977. The Smallest XOR of Any Two Values

Given n values, print the SMALLEST a[i] XOR a[j] over all pairs of different positions.

3 10 5 25 2 8 -> 1 3 xor 2 0 1073741823 -> 1073741823 7 7 7 -> 0 1 2 4 8 -> 3 1 xor 2

The first line is worth comparing with problem 976, which has the same input and answers 28. Maximising and minimising over the same pairs are not variants of one another here; they want different structures and, as it turns out, the minimum wants no structure at all.

## The trie answer

Insert everything with a counted binary trie, then for each value walk down preferring the SAME bit, as in problem 975. That is O(30 n) and it is correct.

## Sorting is smaller, and the proof is the lesson

Sort the values. Then the answer is the smallest XOR of two ADJACENT entries.

sort a best = a[0] xor a[1] for i from 1 to n-2: best = min(best, a[i] xor a[i+1])

Why a non-adjacent pair can never win

Take any three values in sorted order, x < y < z, and let b be the highest bit at which x and z differ. Above b they agree, and at b we have x with a 0 and z with a 1, since x is the smaller. So

x XOR z >= 2^b

Now y lies between them, so y agrees with both above bit b, and its own bit b is either 0 or 1.

· If y has a 1 at bit b, then y and z agree at bit b and everywhere above it, so y XOR z < 2^b <= x XOR z. · If y has a 0 at bit b, then x and y agree at bit b and above, so x XOR y < 2^b <= x XOR z.

Either way one of the two closer pairs beats the outer pair. Applying that repeatedly to any pair with something between them shows a minimising pair has nothing between it, which is exactly adjacency in sorted order.

What that saves

Sorting is n log n comparisons and O(1) extra space. The trie is 30 n steps and, at n = 100000, up to 1 + 30 n = 3000001 nodes at 16 bytes each for two links, which is 3000001 * 16 = 48000016 bytes, about 48 MB, to answer a question one sort settles.

The trie is still the right tool for problem 976, where the MAXIMUM is wanted, because the exchange argument above says nothing about maximising: the largest XOR is routinely between values far apart in sorted order, as 5 and 25 are in the first example.

## The boundaries

Two equal values give 0, which is the smallest possible answer and is reached whenever any value repeats. n = 2 has exactly one pair, and the loop above must still produce it, which is why best is initialised from the first adjacent pair rather than from a large sentinel that a careless loop might never replace.

## Overflow

Nothing here overflows. Every value and every answer is below 2^30 = 1073741824, inside the 2147483647 limit of a signed 32 bit integer.

## Cost

Time O(n log n) for the sort plus O(n) for the sweep. Space O(1) beyond the input.

Constraints - `2 ≤ n ≤ 100000` - `0 ≤ each value ≤ 1073741823`, which is `2^30 - 1` - Values may repeat, and two equal values form a pair whose XOR is 0.