Chef and Destruction
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Arrays have fallen out of Chef's good books, and he plans to destroy all arrays he possesses. He is left with the last array A, consisting of N positive integers. In order to destroy the array, he can perform the following 2 types of operations any number of times.
- Choose any 2 elements, say X and Y, from the given array A such that X != Y, and remove them, or
- Choose any 1 element, say X, from A, and remove it.
In order to destroy the array as quickly as possible, Chef is interested in knowing the minimum number of operations required to destroy it. Please help him achieve this task.
The first line of input contains a single integer T denoting the number of test cases. First line of each test case contains a single integer N — the number of integers in the array A.
Second line of each test case contains N space separated integers denoting the array A.
For each test case, output the required answer in a new line.
- 1 ≤ T ≤ 50000
- 1 ≤ N ≤ 50000
- 1 ≤ Ai ≤ 109
- sum of N over all test cases does not exceed 5 × 105
Input 3 2 1 2 2 1 1 3 1 2 3 Output 1 2 2
- Test 1: In an operation, Chef can choose 2 elements X and Y such that X = 1 and Y = 2 and can destroy them as X != Y.
- Test 2: Chef cannot choose 2 elements X and Y such that X != Y. So, he has to use the second operation twice in order to destroy the array.
|Tags||cook66, easy, greedy, ma5termind|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.