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\limits_{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
2 2 1 3 1 2 2 2 1
1 0
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 \leq 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 \leq K\). Therefore, we don't need to add any non-negative integer to \(A\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor