SPCJ - Gopu and Create Collections Part Two
Little Gopu likes to play very much. As you know he only plays with numbers. So he is given n numbers. Now he tries to group the numbers into collections where each collection contains exactly two numbers. He can form the collection of two numbers a and b (a <= b), if and only if b is either 2 * a or 2 * a + 1.
Note that you can not use a single number in forming of more than one collections. Eg. 1, 2, 4 He can divide the numbers into a single collection only either [1, 2] or [2, 4] because each collection requires exactly two numbers, and each number has to be used only once in a group.
Given n numbers, Find out how many maximum number of collections he can form ?
T: number of test cases.
For each test case, First line will contain n : (1 <= n <= 10^5)
Then next line will contain n numbers single space seperated. Range of each number will be between 1 and 10^18.
Sum of n over all the tests will be atmost 10^6. So number of test cases are decided on this criteria.
For each test case, output maximum number of collections that can be formed.
1 2 4
1 2 4 8
Nice One :)
nice greedy :)
I am getting NZEC, but I have tested my code for various test cases and it is running well. I have tested my code on Ideone also, checked for wild conditions as well. Can anyone help?