973. The Best XOR With a Given Value
You are given n values, then q queries. Each query is a value x. For each
one, print the largest x XOR a[i] over all the stored values.
values 3 10 5 25
x = 5 -> 28 5 xor 25
x = 2 -> 27 2 xor 25
x = 16 -> 26 16 xor 10
## Why trying everything is the wrong shape
Comparing x against all n values is n XORs per query, so 10^10 XORs at
the limits of 100000 values and 100000 queries. Sorting does not help: XOR does
not respect order, and the value nearest x in size can be the worst partner
there is.
## One bit at a time, from the top
XOR decides each bit independently: x XOR y has a 1 at position b exactly
when x and y differ there. So to make the result large, you want to DIFFER
from x at the highest bits you can.
That is what the binary trie makes possible. Descend it from bit 29 down, and at
each step try the child whose bit is the OPPOSITE of x's bit. If that child
exists, take it and record a 1 in the answer. If it does not, the other child is
the only option and the answer gets a 0 there.
node = root, res = 0
for b from 29 down to 0:
want = 1 - ((x >> b) & 1)
if child[node][want] exists:
res = res | (1 << b)
node = child[node][want]
else:
node = child[node][1 - want]
print res
Thirty steps per query, whatever n is.
## Why taking the opposite bit whenever it exists is optimal
Suppose at bit b both choices are available. Taking the opposite bit earns
2^b. The alternative is to take the same bit, earn 0 here, and hope to make it
up below. But everything below adds up to at most
2^(b-1) + 2^(b-2) + ... + 2^0 = 2^b - 1
which is strictly less than 2^b. So no arrangement of the lower bits can
compensate for losing the higher one, and the greedy choice is not merely good,
it is forced.
This argument is the reason the whole family of problems in the rest of this block works, and it is worth being able to state rather than recognise.
## Why the walk can never get stuck
Every stored value occupies a full 30 bit path, so any node the walk reaches has
at least one child: it was created by some value that continued past it. That is
why the else branch needs no test of its own, and it is why the fixed width of
problem 972 matters.
## The boundaries
A single stored value makes every answer x XOR that value, with no choice
anywhere. A stored 0 makes the answer x itself, since x XOR 0 = x. Querying
with a value that is itself stored can still answer 0 only when nothing else is
stored, because a different partner would beat it at its highest differing bit.
## Overflow
Nothing here overflows. Every value and every answer is below 2^30, which is
1073741824, comfortably inside a signed 32 bit integer whose limit is
2147483647. Watch the shift itself: 1 << 29 is fine in a 32 bit int, and only a
width past 31 would need a 64 bit shift.
## Cost
Building is O(30 n). Each query is 30 steps, so the whole run is O(30 (n + q)),
about 6 million steps at the limits.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100000` - `0 ≤ each value and each query ≤ 1073741823`, which is `2^30 - 1`
Input
The first line contains an integer n.
The second line contains n integers.
The third line contains an integer q.
The fourth line contains q query values.
Output
For each query value, in order, print one integer on its own line: the largest XOR of that query with any one of the stored values.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.