Mean equals Median CodeChef Solution – Networking Funda

Problem : Mean equals Median CodeChef Solution

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 1≤i≤N1≤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.

Constraints

• 1≤T≤1041≤T≤104
• 2≤N≤3⋅1052≤N≤3⋅105
• 1≤Ai≤1091≤Ai≤109
• Sum of NN over all test cases does not exceed 3⋅1053⋅105

Sample Input 1 

3
3
1 2 3
4
1 1 3 3
5
1 1000000000 1 1000000000 1

Sample Output 1 

0
4
500000002

Explanation

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.

Get More CodeChef Solution >>

Substring Minimum Function FizzBuzz Solution

Magical Planks Fizzbuzz Solution