[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.

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.