Mediumtrie
Maximum XOR of Two Numbers in an Array
Problem (restated)
Given non-negative integers, return the maximum value of nums[i] XOR nums[j] (i may equal j).
Intuition
Build a binary trie of bits MSB→LSB. For each number, greedily walk opposite bits to maximize XOR.
Approaches
Binary bit trie
Tested onlyTime O(32n)Space O(32n)
Idea. Insert then query (self-XOR is 0; better pairs appear after insert of both). Prefer opposite bit at each level.
Walkthrough. [3,10,5,25,2,8] → 28 (5 XOR 25).
Trade-offs. O(n^2) brute is fine for tiny n; trie is O(n) with 32-bit width.
Solution
type Node = { 0?: Node; 1?: Node };
export function findMaximumXOR(nums: number[]): number {
const root: Node = {};
const insert = (x: number) => {
let n = root;
for (let b = 31; b >= 0; b--) {
const bit = ((x >> b) & 1) as 0 | 1;
n[bit] ??= {};
n = n[bit]!;
}
};
const query = (x: number): number => {
let n = root;
let best = 0;
for (let b = 31; b >= 0; b--) {
const bit = (x >> b) & 1;
const want = (1 - bit) as 0 | 1;
if (n[want]) {
best |= 1 << b;
n = n[want]!;
} else {
n = n[bit as 0 | 1]!;
}
}
return best;
};
let ans = 0;
for (const x of nums) {
insert(x);
ans = Math.max(ans, query(x));
}
return ans;
}
type Node = { 0?: Node; 1?: Node };
export function findMaximumXOR(nums: number[]): number {
const root: Node = {};
const insert = (x: number) => {
let n = root;
for (let b = 31; b >= 0; b--) {
const bit = ((x >> b) & 1) as 0 | 1;
n[bit] ??= {};
n = n[bit]!;
}
};
const query = (x: number): number => {
let n = root;
let best = 0;
for (let b = 31; b >= 0; b--) {
const bit = (x >> b) & 1;
const want = (1 - bit) as 0 | 1;
if (n[want]) {
best |= 1 << b;
n = n[want]!;
} else {
n = n[bit as 0 | 1]!;
}
}
return best;
};
let ans = 0;
for (const x of nums) {
insert(x);
ans = Math.max(ans, query(x));
}
return ans;
}
Template connection
Trie over bit strings for greedy XOR.
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?