# LeetCode 421: Maximum XOR of Two Numbers in an Array ## Problem Restatement We are given an integer array `nums`. Return the maximum value of: ```python nums[i] ^ nums[j] ``` where `^` means bitwise XOR. The indices may be the same according to the source statement: ```python 0 <= i <= j < n ``` Using the same element gives XOR value `0`, so it never hurts the maximum when there are at least two useful values. The source constraints are: ```python 1 <= nums.length <= 2 * 10^5 0 <= nums[i] <= 2^31 - 1 ``` The standard example is: ```python nums = [3, 10, 5, 25, 2, 8] ``` with answer: ```python 28 ``` because: ```python 5 ^ 25 = 28 ``` ## Input and Output | Item | Meaning | |---|---| | Input | Integer array `nums` | | Output | Maximum XOR value of two numbers | | Operation | Bitwise XOR | | Values | Non-negative 31-bit integers | Example function shape: ```python def findMaximumXOR(nums: list[int]) -> int: ... ``` ## Examples Example 1: ```python nums = [3, 10, 5, 25, 2, 8] ``` The answer is: ```python 28 ``` One best pair is: ```python 5 ^ 25 ``` In binary: ```text 00101 ^ 11001 = 11100 ``` `11100` in decimal is: ```python 28 ``` Example 2: ```python nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70] ``` The answer is: ```python 127 ``` ## First Thought: Try Every Pair The direct approach is to test every pair: ```python nums[i] ^ nums[j] ``` and keep the largest value. This is simple, but it takes: ```python O(n^2) ``` With `n` up to `2 * 10^5`, this is too slow. We need to use the bit structure of XOR. ## Key Insight XOR is maximized by making higher bits equal to `1`. A bit in `a ^ b` is `1` exactly when the two bits are different. So we build the answer from the highest bit to the lowest bit. At each bit position, we ask: Can the maximum XOR have this bit set to `1` while keeping the higher bits we already chose? If yes, we keep it. If no, we leave it as `0`. ## Prefix Idea Suppose we only care about the top bits seen so far. For each number, keep its prefix up to the current bit. Then try a candidate answer: ```python candidate = answer | (1 << bit) ``` We need to know whether there are two prefixes `p` and `q` such that: ```python p ^ q == candidate ``` This can be rearranged as: ```python q = p ^ candidate ``` So if we store all prefixes in a set, we can check whether a matching prefix exists. ## Algorithm Initialize: ```python answer = 0 mask = 0 ``` Then scan bits from `30` down to `0`. For each bit: 1. Add this bit to the mask. 2. Store all prefixes: ```python num & mask ``` 3. Try setting this bit in the answer: ```python candidate = answer | (1 << bit) ``` 4. Check if there are two prefixes that XOR to `candidate`. 5. If yes, update: ```python answer = candidate ``` At the end, return `answer`. ## Correctness The algorithm builds the maximum XOR value from most significant bit to least significant bit. Assume that before processing a bit, `answer` is the largest possible XOR prefix for all higher bits. The algorithm tries to set the current bit to `1`, forming `candidate`. If there are two number prefixes whose XOR equals `candidate`, then some pair of numbers can achieve the higher-bit pattern represented by `candidate`. Since setting a higher bit to `1` gives a larger value than any choice in lower bits, the greedy choice is optimal. If no such pair exists, then no pair can achieve that higher-bit pattern, so the current bit must remain `0`. This preserves the invariant that `answer` is the largest achievable XOR prefix after each bit. After all bits are processed, every bit of the maximum XOR has been decided, so `answer` is the maximum possible XOR value. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(31n)` | We scan all numbers for each bit | | Space | `O(n)` | The prefix set stores up to `n` values | Since `31` is constant, the time complexity is usually written as: ```python O(n) ``` ## Implementation ```python from typing import List class Solution: def findMaximumXOR(self, nums: List[int]) -> int: answer = 0 mask = 0 for bit in range(30, -1, -1): mask |= 1 << bit prefixes = {num & mask for num in nums} candidate = answer | (1 << bit) for prefix in prefixes: if prefix ^ candidate in prefixes: answer = candidate break return answer ``` ## Code Explanation We start with: ```python answer = 0 mask = 0 ``` `answer` stores the best XOR prefix found so far. `mask` keeps only the bits we are currently considering. We process bits from high to low: ```python for bit in range(30, -1, -1): ``` The largest value is at most `2^31 - 1`, so bit `30` is the highest relevant bit. We extend the mask: ```python mask |= 1 << bit ``` Then we collect prefixes: ```python prefixes = {num & mask for num in nums} ``` The candidate tries to make the current bit `1`: ```python candidate = answer | (1 << bit) ``` Then we test whether two prefixes can produce that candidate: ```python if prefix ^ candidate in prefixes: ``` If true, the current bit can be `1`, so we keep it: ```python answer = candidate ``` Finally: ```python return answer ``` ## Alternative Trie Solution A binary trie also works. Insert each number into a trie by bits. For each number, greedily walk the opposite bit when possible, because opposite bits produce XOR bit `1`. ```python from typing import List class TrieNode: def __init__(self): self.child = [None, None] class Solution: def findMaximumXOR(self, nums: List[int]) -> int: root = TrieNode() for num in nums: node = root for bit in range(30, -1, -1): b = (num >> bit) & 1 if node.child[b] is None: node.child[b] = TrieNode() node = node.child[b] best = 0 for num in nums: node = root value = 0 for bit in range(30, -1, -1): b = (num >> bit) & 1 want = b ^ 1 if node.child[want] is not None: value |= 1 << bit node = node.child[want] else: node = node.child[b] best = max(best, value) return best ``` The prefix-set solution is shorter. The trie solution is often easier to generalize to online queries. ## Testing ```python def test_find_maximum_xor(): s = Solution() assert s.findMaximumXOR([3, 10, 5, 25, 2, 8]) == 28 assert s.findMaximumXOR([ 14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70, ]) == 127 assert s.findMaximumXOR([0]) == 0 assert s.findMaximumXOR([2, 4]) == 6 assert s.findMaximumXOR([8, 10, 2]) == 10 assert s.findMaximumXOR([7, 7, 7]) == 0 assert s.findMaximumXOR([0, 2147483647]) == 2147483647 print("all tests passed") ``` ## Test Notes | Test | Why | |---|---| | `[3,10,5,25,2,8]` | Standard example | | Larger mixed array | Checks many bit patterns | | Single number | Same index gives XOR `0` | | `[2,4]` | Simple two-number case | | `[8,10,2]` | Best pair may involve smaller value | | Duplicates only | XOR of equal values is `0` | | Maximum 31-bit value | Checks highest relevant bit |