976. The Largest XOR of Any Two Values
Given n values, print the largest a[i] XOR a[j] over all pairs of different
positions.
3 10 5 25 2 8 -> 28 5 xor 25
0 1073741823 -> 1073741823
7 7 7 -> 0
1 2 4 8 -> 12 4 xor 8
## The pair loop
Trying every pair is n (n - 1) / 2 XORs, which at n = 100000 is 4999950000,
about five billion, and each one is cheap but there are far too many of them.
## Insert as you go, and query against what is already there
Problem 973 answers, in 30 steps, "what is the best partner for x among the
stored values". So walk the array once, and for each value ask that question
against the values seen BEFORE it, then insert it.
insert a[0]
best = 0
for i from 1 to n-1:
best = max(best, bestXorAgainstTrie(a[i]))
insert a[i]
print best
## Why considering only earlier partners loses nothing
Every unordered pair {i, j} with i < j is examined exactly once: at step j,
when a[i] is already in the trie. The pair is never examined twice, and no pair
is missed, so the maximum over what is examined is the maximum over all pairs.
Inserting BEFORE querying would also be correct here, because a[i] XOR a[i] is
0 and cannot beat a real pair unless every pair is 0, in which case the answer is
0 anyway. It is still the wrong habit: in problem 979, which prints one answer
per position, inserting first makes every answer 0.
## The first value
Insert a[0] before the loop, or the first query runs against an empty trie and
the walk has no child to take. The statement guarantees n is at least 2 so that
a pair exists at all.
## Overflow
Nothing here overflows. Values and answers are below 2^30 = 1073741824, inside
the 2147483647 limit of a signed 32 bit integer. Note that the PAIR COUNT of
4999950000 quoted above does exceed it, which is why problem 980, which counts
pairs rather than maximising over them, needs 64 bits and this does not.
## Cost
Time O(30 n), one insertion and one query of 30 steps each per value. Space is
at most 1 + 30 n = 3000001 nodes.
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.
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer: the largest XOR obtainable from two values at different positions in the list.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.