Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
For each query x, find the array element that maximizes x ^ element. Brute force tests x against every element: O(n) per query, O(n·q) total. The optimal answer inserts all numbers into a binary trie (one node per bit, most-significant first) and, for each query, walks the trie greedily taking the OPPOSITE bit at every level when it exists — that sets the highest possible bits of the XOR. Build is O(n·B); each query is O(B) where B is the bit width.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you see that maximizing XOR is a per-bit greedy decision (take the opposite bit, high to low) and can back it with a binary trie so each query is O(B) instead of O(n).
Where candidates slip
Doing the O(n) scan per query and stopping there, or building the trie but going to the SAME bit instead of the opposite, or processing bits least-significant first so the greedy choice is no longer optimal.
How to stand out
State the brute force and its O(n·q) cost, then explain why opposite-bit-from-the-top is optimal (a high bit dominates), and note the trie answers each query in O(B) after an O(n·B) build.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMaximize x XOR elementHow many queries?OneManyExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Scan Every Element Per Query
1Hint 1Explore hintHide hint
For a single query x, how would you find the best partner? Just try them all and keep the largest XOR.
2Hint 2Explore hintHide hint
Loop over every element, compute x ^ element, track the maximum.
3Hint 3Explore hintHide hint
Now repeat that scan for each of the q queries. That's n·q work — fine for tiny inputs, too slow at 10⁵ × 10⁵.
A · Core idea
Translate the question directly: for each query value x, walk the entire array, compute x ^ arr[i] for every element, and keep the largest.
Why it's the natural first attempt. The problem literally asks for the maximum of x ^ arr[i] over all i. A linear scan that evaluates exactly that expression for every element is correct by construction — no insight required.
Why it doesn't scale. A single scan is O(n), which is great for one query. But with up to 10⁵ queries against up to 10⁵ elements, the total is n·q ≈ 10¹⁰ XOR operations. That blows the time limit. The fix is to stop re-scanning the whole array for every query and instead preprocess the numbers so each query only inspects B bits.
The bridge to the trie. Notice that for a fixed x, the best partner is decided bit by bit: at the highest bit we'd love an element whose bit is the opposite of x's. The brute force rediscovers that ranking from scratch every time; a trie bakes the bit structure in once.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [0, 2, 5, 7], x = 3Interactive diagram
Per-query linear scan
elem 0Every query re-walks the whole array — the work the trie removes.
6C · Code with teaching comments
Reference implementation previewpublic int[] maxXor(int[] arr, int[] queries) { int[] result = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int best = 0; for (int a : arr) {Explore the full codeHide the full code
D · Why it works and complexityO(n·q) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Maximizing an XOR is a most-significant-bit-first decision: the partner you want disagrees with x as high up as possible. Brute force re-derives that for every query — the trie remembers it.
ComplexityO(n·q) time, O(1) space — Each query scans all n elements doing O(1) XOR work; q queries give n·q ≈ 10¹⁰ in the worst case — far beyond a one-second budget.
E · Edge cases and pitfalls3Initializing best to a wrong sentinel — start at 0 (XOR is non-negative) or at the first computed XOR.Explore edge casesHide edge cases
Pitfalls
- Initializing best to a wrong sentinel — start at 0 (XOR is non-negative) or at the first computed XOR.
- Re-scanning the array per query when q and n are both large — this is the O(n·q) trap.
- Returning an index instead of the maximum XOR value.
Approach 2 of 2 · Optimal
Binary Trie — Greedy Opposite-Bit Walk (Optimal)
1Hint 1Explore hintHide hint
XOR's bit is 1 only when the two bits differ. So to maximize x ^ y, at each bit you want y's bit to be the opposite of x's.
2Hint 2Explore hintHide hint
Store every number in a binary trie: depth = bit position, two children (0 and 1), inserted most-significant bit first.
3Hint 3Explore hintHide hint
To query x, descend from the root: at each level try the child equal to the OPPOSITE of x's bit (set that result bit); if it's missing, follow the only child available. B levels → O(B) per query.
A · Core idea
Preprocess the array into a binary trie, then answer each query by greedily chasing the opposite bit.
Why opposite-bit-from-the-top is optimal. XOR yields a 1 in a position exactly when the two operands differ there. A 1 in a higher position is worth more than all lower positions combined (2^k > 2^k − 1 = sum of all lower bits). So to maximize x ^ y, the single most valuable thing is to make the highest bit of the result a 1 — which means picking a y whose top bit differs from x's. Lock that in, then recurse on the next bit with the same logic. This greedy choice never needs revisiting because no combination of lower bits can ever beat one higher bit.
Why a trie. We need to ask, at each level, 'does the set contain a number that, so far, matches the prefix I've committed to AND has the opposite bit next?' A trie keyed by bits answers exactly that in O(1) per level: the children of the current node ARE the numbers consistent with the prefix walked so far. Following the opposite child when it exists keeps us on the best possible partner; when it's absent we're forced to the same bit and that position contributes 0.
Why most-significant first. Insertion and query must agree on bit order, and the greedy argument only holds top-down. Inserting and querying from the MSB means the first decision is the most significant bit, exactly where the greedy payoff is largest.
Width discipline. Use a fixed B (30 covers 10⁹; 31 is safe). Loop i from B down to 0 for both insert and query so leading zeros are represented consistently.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [0, 2, 5, 7] inserted; query x = 3 (011), using 3 bitsInteractive diagram
Greedy descent for x = 3 (011)
bit 2 (val 4): x bit = 0At each level branch to the bit opposite x's; set the result bit when that branch exists.
6C · Code with teaching comments
D · Why it works and complexityO((n + q)·B) timeO(n·B) spaceOpen the invariant and proofExplore the proofHide the proof
A bitwise trie turns 'find the most opposite number' into a single root-to-leaf walk: at every level greedily branch away from the query's bit. The whole optimization is recognizing that maximizing XOR is a high-bit-first greedy decision, and a trie is the structure that makes each greedy step O(1).
ComplexityO((n + q)·B) time, O(n·B) space — Inserting n numbers touches B nodes each → O(n·B). Each of the q queries descends B levels → O(q·B). Space is the trie: at most n·B nodes. With B ≈ 30 this is effectively linear.
E · Edge cases and pitfalls7arr = [8], x = 1 — Only one path exists; the walk is forced to 8 and returns 1 ^ 8 = 9.Explore edge casesHide edge cases
Edge cases handled
arr = [8], x = 1Only one path exists; the walk is forced to 8 and returns 1 ^ 8 = 9.arr = [5, 5, 5], x = 5Every element equals x; no opposite bit is ever available, so the walk yields 5 ^ 5 = 0.arr = [0], x = 0All-zero number and query; no differing bit possible → result 0.
Pitfalls
- Going to the SAME bit instead of the opposite — that minimizes XOR rather than maximizing it.
- Processing bits least-significant first — the greedy choice is only optimal top-down.
- Using too few bits for B and silently dropping the high bits of large numbers.
- Forgetting to fall back to child[b] when child[want] is null — leads to a null-pointer walk.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewstatic class Trie { Trie[] child = new Trie[2]; } static final int B = 30; // 10^9 fits in 30 bitsExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Greedy toward the same bit
XOR is 1 only when bits differ. Taking the child equal to x's bit makes the XOR bit 0 and minimizes the result.
Explore the code comparisonHide the code comparison
Greedy toward the same bit
XOR is 1 only when bits differ. Taking the child equal to x's bit makes the XOR bit 0 and minimizes the result.
Don't write this
int b = (x >> i) & 1;
if (node.child[b] != null) node = node.child[b]; // same bit → minimizesWrite this instead
int want = 1 - ((x >> i) & 1);
if (node.child[want] != null) { res |= (1 << i); node = node.child[want]; }2Bits processed low-to-high
The greedy 'take the opposite bit' is only globally optimal from the most significant bit down; reversing the order can pick a worse high bit.
Explore the code comparisonHide the code comparison
Bits processed low-to-high
The greedy 'take the opposite bit' is only globally optimal from the most significant bit down; reversing the order can pick a worse high bit.
Don't write this
for i in range(0, B + 1): # LSB first — greedy no longer optimal
...Write this instead
for i in range(B, -1, -1): # MSB first
...3Width too small
If B is smaller than the number of significant bits, the top bits never enter the trie and the maximum XOR is undercounted.
Explore the code comparisonHide the code comparison
Width too small
If B is smaller than the number of significant bits, the top bits never enter the trie and the maximum XOR is undercounted.
Don't write this
B = 16 # 10^9 needs ~30 bits
Write this instead
B = 30 # covers values up to 10^9
Revise
Carry the pattern into the interview
Pattern to remember
Greedy high-bit choice over a binary (bitwise) trie
Code pattern to memorize
build: insert every num bit-by-bit, MSB → LSB
query(x):
res = 0
for bit from B down to 0:
want = 1 - ((x >> bit) & 1) # opposite bit maximizes XOR
if child[want] exists: res |= (1 << bit); go to child[want]
else: go to child[1 - want]
return resRules to remember
- 1XOR of two bits is 1 only when they differ. To maximize x ^ y, you want y's bit to be the OPPOSITE of x's bit at every position.
- 2Process bits most-significant first — a single high bit outweighs all lower bits combined, so the greedy choice is locally and globally optimal.
- 3Only set
res |= (1 << bit)when the opposite branch actually exists; otherwise you must follow the same-bit branch and that position contributes 0. - 4Fix the bit width
Bfrom the constraints (values ≤ 10⁹ → 30 bits is enough; use 30 or 31). Looping too few bits drops the high bits of the answer. - 5Brute force first (O(n) per query) to show the progression, then introduce the trie as the way to answer each query in O(B).
Use this pattern when
- Repeated 'maximum/minimum XOR of x against a set' queries
- You can preprocess the set once and answer many queries fast
- Max-XOR-pair problems (insert as you scan, query against what's seen)
- Anything where a per-bit greedy decision composes the optimum
Choose another pattern when
- A single query over a single array → just one linear scan, no trie
- You need the XOR subset/total, not a max against a target → think prefix-XOR or parity
- Range/index constraints on the partner (l ≤ a ≤ b ≤ r) → that's Maximizing XOR, a closed-form, not a trie
- Memory is tight and B·n nodes won't fit → consider sorting-based or offline tricks
Interview takeaway
Max-XOR against a set is the canonical bit-trie problem: store numbers by their bits, then greedily chase the opposite bit from the top down. The same trie powers Maximum XOR of Two Numbers and Maximum XOR With an Element From Array — learn it once, reuse everywhere.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternBitwise trie + high-bit-first greedy. Whenever you must maximize (or minimize) an XOR of a value against a set, store the set by bits and walk toward the opposite (or same) bit from the MSB down. This is the backbone of Maximum XOR of Two Numbers and its constrained variants.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Maximum XOR of Two Numbers in an ArrayComing soonInsert each number then query it against the trie of the rest — same greedy walk, no separate query list.
- Maximum XOR With an Element From ArrayComing soonAdd an upper-bound constraint (element ≤ m). Sort queries and insert numbers up to m offline, then query the trie.
- Maximizing XORWhen the partner is constrained to a range l..r, the answer is a closed form from the leading differing bit — no trie needed.