DSA problem
Maximum XOR of Two Numbers in an Array
Given an integer array nums, return the maximum result of nums[i] XOR nums[j] where 0 <= i <= j < n. The XOR of two integers is computed bit by bit, returning a 1 where the bits differ and a 0 where they match — so to maximize the XOR, we want as many high-order bit positions as possible to have differing bits.
A brute-force solution tries every pair and computes the XOR in O(n^2) time, which is far too slow for n up to 2 * 10^5. The clever trick is to repurpose a trie over the binary representations of the numbers: each path from the root to a leaf encodes a 32-bit integer, one bit per level, with the most significant bit at the root.
With every number in this binary trie, the maximum XOR partner for a query x can be discovered greedily. At each bit position from MSB to LSB, look at x's bit; the partner that maximizes XOR has the opposite bit. If a child for the opposite bit exists in the trie, descend into it (the XOR bit at this level is 1); otherwise descend into the same-bit child (the XOR bit is 0). After 32 levels you have constructed a partner whose XOR with x is the largest possible, and you can record the maximum across all queries.
The trie holds O(32 * n) nodes and answering one query is O(32). Inserting all numbers takes O(32 * n) and querying each number against the partial trie built so far gives the same total budget, so the algorithm runs in O(32 * n) = O(n) time with O(32 * n) space — a dramatic improvement over the quadratic baseline.
Examples
nums = [3,10,5,25,2,8]28nums = [14,70,53,83,49,91,36,80,92,51,66,70]127nums = [0]0Constraints
- 1 <= nums.length <= 2 * 10^5
- 0 <= nums[i] <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.