# One-XOR Deletions Codechef Solution

### We Are Discuss About CODECHEF SOLUTION

One-XOR Deletions Codechef Solution

## Problem

Chef has with him an array A of length N. In one move, he can delete any element from A.

Find the minimum number of deletions Chef must make so that the following condition holds:

• Let B denote the resulting array, and M be the length of B.
• Then, B_i \oplus B_j \leq 1 for every 1 \leq i, j \leq M.

Here, \oplus denotes the bitwise XOR operation.

For example, [3, 3, 3] and [6, 7, 6, 7] are valid final arrays, while [1, 2] and [6, 7, 8] are not (because 1 \oplus 2 = 3 and 7\oplus 8 = 15, respectively).

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains a single integer N, denoting the length of array A.
• The second line contains N space-separated integers A_1, A_2, \ldots, A_N — the elements of array A.

### Output Format

For each test case, output on a new line the answer: the minimum number of deletions required so that the given condition is satisfied.

### Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 3\cdot 10^5
• 0 \leq A_i \leq N
• The sum of N over all test cases won’t exceed 3\cdot 10^5.

### Sample 1:

Input

Output

4
4
2 2 2 2
5
3 4 3 4 4
5
1 2 3 4 0
6
5 5 5 6 6 6

0
2
3
3


### Explanation:

Test case 1: The given array already satisfies the condition, no deletions need to be done.

Test case 2: Chef can delete both the 3‘s to make the array [4, 4, 4], which satisfies the condition.

Test case 3: Chef can use three moves as follows:

• Delete the 1, the array is now [2, 3, 4, 0].
• Delete the 4, the array is now [2, 3, 0].
• Delete the 0, the array is now [2, 3] which satisfies the condition.

It can be verified that using two or less deletions cannot give an array that satisfies the condition.

Test case 4: Chef must either delete all the 5‘s or all the 6‘s.

## One-XOR Deletions Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW