Minimum additions

★★★★★

2.5

73 votes

Arrays, Data Structures, 1-D

Details

Submissions

Discussion

Editorial

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\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

$1 \leq T \leq 10 \\ 1 \leq N \leq 2 \times 10^5 \\ 1 \leq A[i] \leq 10^9 \\ 0 \leq K \leq 10^9$

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 \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$ .