## Karan Khosla

BAN USER- 0of 0 votes

AnswersMaximum Pairs

You are given N pencils. You have to make pairs of pencils.

The condition for making pairs is:

If(a,b) is any pair of pencils then b >= 2 * a. Here a and b are the sizes of pencils.

Now you have to find out the number of such pairs and the number of pencils which could not be paired with any pencils.

Note:

You need to pair the pencils in such a manner that the maximum number of pairs are formed.

Input Format:

The first line consists of number of test case T.

Each test case consist of:

- First line consists of a single integer N.

- Second line consists of N space-separated integers denoting the size of pencils Si.

Output Format:

For each test case, print two space-separated integers, first denoting the number of pairs formed and second denoting the number of unpaired pencils.

Answer for each test case should come in a new line.

Constraints

1<T<=10

1<=N<=10^5

0<=Si<=10^5

Sample Input

2

5

1 2 3 4 5

4

1 2 4 4

Sample Output

2 1

2 0

Explanation

In the first test case:-

we can form the following pairs:

(1, 3), (2, 4) and 5 remains unpaired hence maximum pairs are 2

In second test case:-

(1, 4), (2, 4) are two pairs hence no pencil left unpaired

- Karan Khosla in United States for 4`public class Test { public static void main(String[] args) { } static int[] solve(int[] arr) { // the value at first index of array to be returned is number of pairs // formed and value at second index is unpaired swords. } }`

| Report Duplicate | Flag | PURGE

Java Developer Java

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window