Algorithm

Problem link- https://www.spoj.com/problems/IITKWPCO/

IITKWPCO - Create Collections

#ad-hoc-1

 

Little Feluda likes to play very much. As you know he only plays with numbers. So he is given n numbers. Now tries to group the numbers into disjoint collections each containing two numbers. He can form the collection containing two numbers iff small number in the collection is exactly half of large number.

Given n numbers, Find out how many maximum number of collections he can form ?

Input

T: number of test cases. (1 <= T <= 100).

For each test case:

First line will contain n :  (1 <= n <= 100)

Then next line will contain n numbers single space separated. Range of each number will be between 1 and 10^6.

Output

For each test case, output maximum number of collections that can be formed.

Example

Input:
2
2
1 2
3 
1 2 4

Output:
1
1

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

T = int(input())
for _ in range(T):
    N = int(input())
    a = sorted(list(map(int, input().split())))
    result, ptr = 0, 0
    for i in range(0, N):
        while ptr < N - 1 and a[ptr] < 2 * a[i]:
            ptr += 1
        if a[i] * 2 == a[ptr]:
            result += 1
            a[ptr] = -1
    print(result)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
2
1 2
3
1 2 4

Output

x
–
+
cmd
1
1
Advertisements

Demonstration

SPOJ Solution-Create Collections-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python