Minimum additions

 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 $\lfloor \frac{\sum _{i=1}^N{A}_i}{N}\rfloor$. Here $\lfloor .\rfloor$ 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

$$\begin{gathered} 1\le T\le 10 \\ 1\le N\le 2\times {10}^5 \\ 1\le A[i]\le {10}^9 \\ 0\le K\le {10}^9 \end{gathered}$$

Sample Input

2
2 1
3 1
2 2
2 1

Sample Output

1
0

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In the first test case, we have $N=2$, $K=1$, $A=[3,1]$. The current floor of average of $A$ is $\lfloor \frac{3+1}{2}\rfloor =2>K$.

If we add the element $1$ to the array, the array becomes $[3,1,1]$. The floor of average of $A$ is $\lfloor \frac{3+1+1}{3}\rfloor =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=[2,1]$. The current floor of average of $A$ is $\lfloor \frac{2+1}{2}\rfloor =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 = mid-1;

                }

                else{   

                    L = mid+1;

                }

            }

            cout << extra-N << endl;

        }

    }

}