# 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