Problem:-

You are given an array

$A$

of

$N$

positive integers. Your task is to add a minimum number of non-negative integers to the array such that the floor of an average of array

$A$

becomes less than or equal to

$K$

.

The floor of an average of array

$A$

containing

$N$

integers is equal to

$⌊\frac{\sum _{i=1}^{N}{A}_{i}}{N}⌋$

. Here

$⌊.⌋$

is the floor function. You are given

$T$

test cases.

Input format

• The first line contains a single integer
$T$

that denotes the number of test cases. For each test case:

• The first line contains two space-separated integers
$N$

and

$K$

denoting the length of the array and the required bound.

• The second line contains
$N$

space-separated integers denoting the integer array

$A$

Output format

For each test case (in a separate line), print the minimum number of non-negative integers that should be added to array

$A$

such that the floor of an average of array

$A$

is less than or equal to

$K$

.

Constraints

$1\le T\le 10\phantom{\rule{0ex}{0ex}}1\le N\le 2×{10}^{5}\phantom{\rule{0ex}{0ex}}1\le A\left[i\right]\le {10}^{9}\phantom{\rule{0ex}{0ex}}0\le K\le {10}^{9}$

Sample Input
`22 13 12 22 1`
Sample Output
`10`
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, we have

$N=2$

$K=1$

$A=\left[3,1\right]$

. The current floor of average of

$A$

is

$⌊\frac{3+1}{2}⌋=2>K$

.

$1$

to the array, the array becomes

$\left[3,1,1\right]$

. The floor of average of

$A$

is

$⌊\frac{3+1+1}{3}⌋=1\le K$

. Therefore, the minimum number of non-negative integers we need to add in this case is

$1$

.

In the second test case, we have

$N=2$

$K=2$

$A=\left[2,1\right]$

. The current floor of average of

$A$

is

$⌊\frac{2+1}{2}⌋=1\le K$

. Therefore, we don’t need to add any non-negative integer to

$A$

.

(c++)   Code:-

#include <iostream>
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
int main() {

// this is for decreasing time
// three lines use only for decrease time
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
long long int N,K;
cin >> T;
while(T–){
cin >> N >> K;
long long int i, temp, sum=0;
for(i=0; i<N; i++){
cin >> temp;
sum+=temp;
}
long long int floor;
floor = sum/N;
if(floor <= K)
cout << 0 << endl;
else{
long long int R = 1e18,extra,L=N,mid;
while(L<=R){
mid = (L+R)/2;
floor = sum/mid;
if(floor <= K){
extra = mid;
R = mid1;
}
else{
L = mid+1;
}
}
cout << extraN << endl;
}
}
}