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 1Bi​⊕Bj​≤1 for every $1\le i,j\le 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_NA1​,A2​,…,AN​ — 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

Sample 1:

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.