XOR is minimized for adjacent sorted elements
Find the minimum xor of a pair of numbers from the given array.
Suppose the minimum xor is between a pair of numbers $a$ and $c$. WLOG, Assume $a < c$.
We claim that there is no $b$ in the array such that $a < b < c$.
Assume that there does exist $b$ in betwen these numbers. Consider the most significant set-bit of $a \oplus c$. Assume that it’s at index $p$. A set bit in the xor indicates a bit difference at that position in the original numbers. Since $a < c$, and this is the first bit difference in decreasing order of significant bits, it’s clear that $a$ had a $0$ at that position, while $c$ had a $1$ at that position. What is the bit value of $b$ at position $p$?
- If it is $0$, we could do $a \oplus b$ and the resulting number will have the bit at position $p$ as $0$.
- If it is $1$, we could do $b \oplus c$ and the resulting number will have the bit at position $p$ as $0$.
Hence, it’s always possible to improve the answer by either deleting $a$ or $c$ and pairing up the remaining number with $b$, which eventually turns off the $p^{th}$ bit. Since we had assumed $a \oplus c$ to be minimal, this leads to a contradiction, hence the optimal xor pair will not have any gaps in between them.
To compute minimum xor of all possible pairs, sort the array. The minimum xor pair will now be adjacent to each other.
Let’s look at an example. \[\begin{aligned} a &= 11000111 \\ c &= 11100111 \\ xor &= 00100000 \end{aligned}\]
If there is a $b$ in between $a$ and $c$, it will have the form $11*$.
- Suppose $b = 11000110$. Then, if we do $a \oplus b$, the new xor would be $0000001$.
- Suppose $b = 11100110$, then doing $b \oplus c$ yields $0000001$. In either case, we were able to turn off the $p^{th}$ bit. Sure, some lower order bits were turned on, but remember the expression
$$ 2^{n + 1} = 2^0 + 2^1 + 2^2 + \dots 2^{n} + 1 $$
This means that the power of all the smaller bits combined is not enough to reach the level of $2^{n + 1}$. Hence, if we need to turn on ALL the smaller bits at the expense of turning off the $p^{th}$ bit, we should still take the deal. This is an important observation which is frequently useful in problems involving bitwise operations.
You can find the code here
Depending upon your familiarity with bitwise operations, some of the following things might not be obvious to you.
- Why do we claim that the higher order bits of $b$ (the ones after index $p$) are identical to those of $a$. In fact, why are the bits of $a$ and $c$ after index $p$ identical?
The bits of index $a$ and $c$ after index $p$ are identical, because by definition, $p$ is the index of the highest set bit in the resulting xor. Had there been a bit difference in the higher order bits, the corresponding bit in xor would be set.
Now, why should the bits of $b$ after index $p$ be identical to $a$ or $c$. Let’s prove that it’s identical to $a$ and the rest follows from the previous observation.
Recall the expression, $$ 2^{n + 1} = 2^0 + 2^1 + 2^2 + \dots 2^{n} + 1 $$
Break down $a$ into 2 parts partitioned at index $p$. Now, we have to ensure that $b > a$. So if you were to turn off any of the bit in the part with index $> p$, you would not be able to make the resulting sum greater than $a$, because, remember, power of all smaller bits combined is not enough to match the influence of just 1 single higher order bit. But keep in mind that this argument worked only because we were not allowed to set a bit which is higher than the most significant bit of $c$.
- Why are we only focusing on turning off the $p^{th}$ bit? What if we accidentally turn on a more significant bit of the xor in the process, thereby increasing the xor?
As proved above, the bits of $b$ after index $p$ are identical to $a$ as well as $c$. Hence, the xor of those bits would always be $0$ and we don’t have to worry about accidentally turning on any higher order bits.
- The minimum xor pair will not have any gaps in between them. However, this doesn’t mean that the xor would increase if the absolute difference between numbers increases. For example, $7 \oplus 8 = 15$ while $7 \oplus 9 = 14$ and $8 \oplus 9 = 1$
Binary Spiders can be solved in $O(n^2)$ using this idea. You can submit the $O(n^2)$ code here.
I will add my solution and explanation for $O(n^2)$ after a couple of AC submissions on the practice contest. If you need any hints for this problem, you can ask on my discord server or twitter
The editorial of Binary Spiders mentions this fact. Although I was able to prove it after reading the editorial using the same idea discussed in this blog, I did refer to this comment by Perpetually_Purple to validate that my idea was indeed correct.