975. The Closest Value by XOR
You are given n values, then q queries. Each query is a value x. For each
one, print the SMALLEST x XOR a[i] over all the stored values.
values 3 10 5 25
x = 5 -> 0 5 is stored, and 5 xor 5 is 0
x = 2 -> 1 2 xor 3
x = 16 -> 9 16 xor 25
## One line different from problem 973
973 wants the largest XOR and takes the OPPOSITE bit whenever it exists. Wanting the smallest, take the SAME bit whenever it exists:
node = root, res = 0
for b from 29 down to 0:
same = (x >> b) & 1
if child[node][same] exists:
node = child[node][same] # this bit of the result is 0
else:
node = child[node][1 - same]
res = res | (1 << b) # forced to differ here
## Why the greedy still holds, in the other direction
Agreeing with x at bit b puts a 0 there and costs nothing. Disagreeing puts
a 1 there and costs 2^b. Since everything below adds up to at most
2^b - 1, which is less than 2^b, no saving lower down can pay for a 1 placed
higher up. So agreeing whenever possible is forced, exactly as differing whenever
possible was forced in 973. The two problems are the same argument with the
inequality pointing the other way.
## What "closest" means here, and what it does not
x XOR y small means x and y agree on a long run of TOP bits. That is not
the same as |x - y| being small: 15 and 16 differ by 1 and their XOR is 31,
while 0 and 16 differ by 16 and their XOR is 16. So this is nearness in the
binary tree, not nearness on the number line, and sorting the values would answer
the wrong question.
## The boundary
A query that is itself stored answers 0, because the whole path agrees. That is
the case which makes this problem useful as an exact-membership test as well: the
answer is 0 if and only if x is one of the stored values.
## Overflow
Nothing here overflows. Every value and answer is below 2^30 = 1073741824,
inside the 2147483647 limit of a signed 32 bit integer.
## Cost
Building is O(30 n), each query is 30 steps. Space is at most 3000001 nodes.
## Against problem 977
977 asks for the smallest XOR over all PAIRS of the stored values, which this walk can answer by querying every value in turn, and which sorting answers more simply. That statement explains why.
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 smallest 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.