DCEPCA10 - MAD

Penny has started taking mathematics classes and has got better at it. She now wants to challenge Sheldon at this expertise and make a fool out of him. She writes down a list of numbers as list A and calculates the median of it. The she calculates the absolute deviation of each number from this median value to make list B. Now she finds the median of this list B. She asks Sheldon to find the minimum number of elements he needs to change in list A so that the median of list B becomes equal to 0. Can you help Sheldon do this?

For example:

  • List of numbers (A):  4 5 3 1 2
  • Median of list A = 3
  • List of Absolute Deviation from median (B) = 1 2 0 2 1
  • Median of list B = 1

Note: Median of even length list is the mean of 2 middle values.

Constraints

0 < T ≤ 10
0 < N ≤ 105
0 ≤ A[i] ≤ 109

Input

T Number of test cases followed 2T lines.
First line of test case contains N, size of array.
Second line contains A[0] to A[N-1]  the numbers of the array.

Output

T lines each containing a single number which denotes the minimum number of elements we need to change to get the median of the absolute deviation of numbers from median to be 0.

Example

Input:
2
5
4 5 3 1 2
10
5 5 5 254 5 5 768 5 5 5

Output: 2
0

Added by:dce coders
Date:2012-12-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2014-10-30 18:59:44 nsaini
So many times WA ,running upto 3 test case ...
2013-08-27 03:36:54 Dhruv Chandhok
getting WA :/
code's working fine on ideone....wondering which test case i am missing
2013-05-28 05:15:52 Kartik Khare
getting wrong answer on judge 1 plz help me..
2013-02-19 00:52:30 renzo
what happen when the mean of the two central values is not an integer?
2013-02-08 14:23:14 Prateek Agrawal
Side Note - All numbers are integers
2013-01-30 21:52:03 unXled
there is always a room for improvement ;)
2013-01-21 10:22:18 BOND
phew..after a very long time I have been caught on this type of challenge.. nice one ...
2012-12-30 19:08:39 Avinash Thummala
If possible please take a look at my submission, id -> 8380380. I have tried to handle all the cases, not really sure why I keep getting WA. Any help would be appreciated.
2012-12-28 17:51:19 Akagami
huffff!!!! silly mistake. n=1 case cost me many WA
2012-12-24 08:01:58 Swapnil R.Mehta
@kevin
it depends on your logic!
My O(n)+stl (time=0.74) and,
O(nlogn) (time=0.25)!

Last edit: 2012-12-24 08:05:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.