Mean equals Median solution codechef

Mean equals Median solution codechef


Chef gets confused between mean and median very often, and as a result, he has developed a dislike of arrays whose mean and median are not equal.

Chef has an array AA of NN elements. He can perform the following operation on it:

  • Pick an index 1iN1≤i≤N and increase AiAi by 11.

He would like to obtain an array whose mean and median are equal. Determine the minimum number of operations required to achieve this.

Note: The median of an array AA of length NN is defined as follows: Sort the array AA. Then,

  • If NN is even, the median is the (N2)th(N2)th element
  • If NN is odd, the median is the (N+12)th(N+12)th element

For example, the median of the array [3,4,1,2][3,4,1,2] is 22 and the median of the array [3,4,1][3,4,1] is 33.

Input Format

  • The first line of input contains a single integer TT, denoting the number of testcases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN, denoting the size of the array.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, print a single line containing one integer — the minimum number of operations Chef needs to perform to make the mean and median equal.


  • 1T1041≤T≤104
  • 2N31052≤N≤3⋅105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 31053⋅105

Sample Input 1 

1 2 3
1 1 3 3
1 1000000000 1 1000000000 1

Sample Output 1 



Test Case 11: The mean and median of the array are both 22. They are already equal, so no operations are required.

Test Case 22: It is optimal to apply the operation on 1st1st and 2nd2nd index twice each. The array after applying these operations will be [3,3,3,3][3,3,3,3], which has both mean and median 33.

Leave a Comment

Your email address will not be published.