Understanding Maximum XOR Pair Algorithm: Efficient Computing

1. Introduction and Core Concepts

The maximum XOR pair algorithm is a fundamental bit manipulation technique that finds the pair of numbers in an array that yields the highest possible XOR value. Given an array of integers nums, the goal is to find two elements a and b such that a XOR b is maximized. While the problem statement appears simple, its efficient solution reveals deep insights into binary representation, greedy strategies, and trie-based data structures.

At its core, the XOR (exclusive OR) operation compares two numbers bit by bit. The result has a 1 in each bit position where the input bits differ, and 0 where they are the same. For example, 5 XOR 2 = 7 because 101 XOR 010 = 111. The maximum XOR pair problem exploits a key property of XOR: to maximize the result, we want the two numbers to differ in as many high-order bits as possible. A difference in the most significant bit (e.g., bit 31) contributes far more to the final value than differences in all lower bits combined.

This algorithm matters far beyond coding interviews. It is a canonical example of how bit-level thinking can transform an apparently quadratic problem into a linearithmic one. The brute-force approach checks every pair in O(n²) time, which becomes infeasible for large datasets with millions of integers. The optimized trie-based solution solves the same problem in O(n * w) time, where w is the word size (typically 32 for integers), making it effectively linear. Understanding this algorithm builds intuition for a whole class of problems involving prefix XORs, Hamming distance, and binary search on answer bits, which appear in cryptography, networking, and data compression.

Why XOR Maximization Is Non-Trivial

Unlike finding a maximum sum or maximum product pair, where sorting immediately reveals the answer, XOR has no monotonic relationship with numeric magnitude. The largest numbers in the array do not necessarily form the maximum XOR pair. For instance, in the array [8, 10, 2], the two largest numbers 10 (1010) and 8 (1000) give 2 (0010), while 8 (1000) and 2 (0010) give 10 (1010), which is larger. This non-intuitive behavior means we cannot rely on sorting or simple comparisons.

The problem also introduces the concept of bit significance. A greedy strategy that tries to set the highest possible bit in the answer to 1 is provably optimal. If we can find any pair that differs at bit 31, that pair will be better than any pair that only differs at bits 30 and below, regardless of how many lower bits differ. This greedy-by-bit-position principle underlies both the trie approach and the alternative prefix-set approach using hash sets.

2. How It Works

The efficient maximum XOR pair algorithm is built on two key ideas: a binary trie (also called a prefix tree) and a greedy bit-by-bit search. A binary trie is a tree structure where each node represents a bit, with two children corresponding to 0 and 1. Every number is inserted into the trie according to its 32-bit binary representation, from the most significant bit (MSB) to the least significant bit (LSB). This structure allows us to efficiently query, for any given number, which existing number in the trie would maximize XOR with it.

For a given query number num, the ideal partner is its bitwise complement — the number that has the opposite bit at every position. While the exact complement may not exist in the array, the trie lets us find the closest available match greedily. Starting from the MSB, we attempt to take the opposite branch at each level. If the opposite branch exists (meaning there is at least one number in the trie with the desired bit), we take it and set the corresponding bit in our result to 1. If it does not exist, we are forced to take the same-bit branch, setting the result bit to 0. Because we process bits from high to low, this greedy choice is globally optimal.

The overall algorithm proceeds in two phases. First, we build the trie by inserting all numbers (or incrementally as we iterate). Second, for each number in the array, we query the trie to find its best partner and track the global maximum. An important optimization is to insert numbers incrementally: for each number, first query the trie containing previously seen numbers, then insert the current number. This avoids pairing a number with itself and still guarantees the optimal pair will be found.

The Role of Bit Length and Leading Zeros

To make the trie work correctly, all numbers must be considered with the same bit width, typically 31 bits for non-negative integers (bits 31 down to 0) or 32 bits if negative numbers are allowed. Leading zeros are crucial. For example, the number 2 (10) must be treated as 000...0010 so that it correctly aligns with larger numbers like 8 (1000) at the high-order bits. Without fixed-width padding, the trie would be unbalanced and the greedy logic would fail.

Alternative View: Prefix Set with Greedy Mask

An equivalent formulation avoids an explicit trie and uses hash sets. The idea is to build the answer bit by bit from MSB to LSB. We maintain a candidate answer ans and a mask that progressively reveals more bits. At each step, we try to set the next bit of ans to 1 (i.e., candidate = ans | (1 << i)) and check if there exist two prefixes p1, p2 in the set of masked numbers such that p1 XOR p2 == candidate. This check is done by verifying if p XOR candidate exists in the prefix set for any p. While this method uses O(n) extra space per iteration, it demonstrates the same greedy principle without pointer-based trees.

3. Implementation

Implementing the maximum XOR pair algorithm in Python requires careful handling of bit operations and trie structure. Below are multiple implementations, from the naive baseline to the optimized trie solution, each with detailed comments and HTML-safe escaping.

Brute-Force Baseline for Comparison

The brute-force solution is straightforward but serves as a correctness reference and a performance baseline. It enumerates every pair and is only suitable for small inputs.

def max_xor_brute_force(nums):
    """
    Brute-force O(n^2) solution for maximum XOR pair.
    Checks every pair (i, j) where i < j.
    """
    n = len(nums)
    if n < 2:
        return 0
    
    max_xor = 0
    best_pair = (nums[0], nums[0])
    
    for i in range(n):
        for j in range(i + 1, n):
            current_xor = nums[i] ^ nums[j]
            # Update if we found a larger XOR value
            if current_xor > max_xor:
                max_xor = current_xor
                best_pair = (nums[i], nums[j])
    
    print(f"Best pair: {best_pair} gives XOR = {max_xor}")
    return max_xor

# Example usage
arr = [3, 10, 5, 25, 2, 8]
print(max_xor_brute_force(arr))  # Expected: 28 (5 ^ 25)

Optimized Trie-Based Solution

This is the canonical efficient implementation. We define a TrieNode with two children and insert numbers bit by bit. The query function implements the greedy opposite-bit strategy.

class TrieNode:
    def __init__(self):
        # children[0] -> branch for bit 0, children[1] -> branch for bit 1
        self.children = [None, None]

class BinaryTrie:
    def __init__(self, max_bits=31):
        self.root = TrieNode()
        # max_bits = 31 handles numbers up to 2^31 - 1
        # Use 31 for non-negative ints, 32 if negatives possible
        self.max_bits = max_bits
    
    def insert(self, num):
        """Insert a number into the binary trie, MSB to LSB."""
        node = self.root
        for i in range(self.max_bits, -1, -1):
            # Extract i-th bit: (num >> i) & 1
            bit = (num >> i) & 1
            if node.children[bit] is None:
                node.children[bit] = TrieNode()
            node = node.children[bit]
    
    def query_max_xor(self, num):
        """
        Find the maximum XOR achievable with num 
        against any number already in the trie.
        Greedily prefers opposite bit at each level.
        """
        node = self.root
        xor_val = 0
        for i in range(self.max_bits, -1, -1):
            bit = (num >> i) & 1
            # Desired bit is the opposite (toggle)
            toggled_bit = 1 - bit
            
            # If opposite branch exists, take it and set result bit to 1
            if node.children[toggled_bit] is not None:
                xor_val = xor_val | (1 << i)  # Set i-th bit in result
                node = node.children[toggled_bit]
            else:
                # Otherwise, must follow same-bit path
                node = node.children[bit]
        return xor_val

def find_maximum_xor(nums):
    """Main driver: O(n * w) time, O(n * w) space."""
    if len(nums) < 2:
        return 0
    
    trie = BinaryTrie()
    # Insert first number to initialize trie
    trie.insert(nums[0])
    max_xor = 0
    
    # For each subsequent number, query then insert
    for num in nums[1:]:
        current_best = trie.query_max_xor(num)
        if current_best > max_xor:
            max_xor = current_best
        trie.insert(num)
    
    return max_xor

# Example
nums = [3, 10, 5, 25, 2, 8]
print(find_maximum_xor(nums))  # Output: 28

Hash-Set Based Greedy Implementation

This variant avoids building a trie explicitly and uses the prefix-set greedy method. It is often more concise in Python and uses less pointer overhead.

def find_maximum_xor_hashset(nums):
    """
    Greedy + HashSet approach.
    Builds answer from MSB to LSB using masks and prefix sets.
    Time: O(n * w), Space: O(n)
    """
    max_xor = 0
    mask = 0
    
    # Iterate from most significant bit (31) down to 0
    for i in range(31, -1, -1):
        # Progressively include more bits in the mask
        # mask will be like 100..0, 110..0, 111..0, etc.
        mask = mask | (1 << i)
        
        # Collect all prefixes of length (31 - i) bits
        prefixes = set()
        for num in nums:
            prefixes.add(num & mask)
        
        # Try to set the i-th bit of max_xor to 1
        candidate = max_xor | (1 << i)
        
        # Check if there exist two prefixes p1, p2 such that p1 ^ p2 == candidate
        # This is equivalent to checking if p ^ candidate exists for any p
        found = False
        for p in prefixes:
            if (p ^ candidate) in prefixes:
                found = True
                break
        
        if found:
            max_xor = candidate
    
    return max_xor

# Example
nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]
print(find_maximum_xor_hashset(nums))

Returning the Actual Pair, Not Just the Value

Many applications need the pair itself. This extension stores the original number at the leaf node to retrieve the partner that yields the maximum XOR.

class TrieNodeWithValue:
    def __init__(self):
        self.children = [None, None]
        self.value = None  # Store number at leaf

class BinaryTrieWithPair:
    def __init__(self, max_bits=31):
        self.root = TrieNodeWithValue()
        self.max_bits = max_bits
    
    def insert(self, num):
        node = self.root
        for i in range(self.max_bits, -1, -1):
            bit = (num >> i) & 1
            if node.children[bit] is None:
                node.children[bit] = TrieNodeWithValue()
            node = node.children[bit]
        node.value = num  # Store at leaf
    
    def query_with_partner(self, num):
        """Returns (max_xor_value, partner_number)."""
        node = self.root
        for i in range(self.max_bits, -1, -1):
            bit = (num >> i) & 1
            toggled = 1 - bit
            if node.children[toggled] is not None:
                node = node.children[toggled]
            else:
                node = node.children[bit]
        # At leaf, node.value is the best partner
        partner = node.value
        return (num ^ partner, partner)

def find_max_xor_pair(nums):
    if len(nums) < 2:
        return (0, None, None)
    
    trie = BinaryTrieWithPair()
    trie.insert(nums[0])
    best_xor = 0
    best_pair = (nums[0], nums[0])
    
    for num in nums[1:]:
        xor_val, partner = trie.query_with_partner(num)
        if xor_val > best_xor:
            best_xor = xor_val
            best_pair = (num, partner)
        trie.insert(num)
    
    return (best_xor, best_pair[0], best_pair[1])

xor_val, a, b = find_max_xor_pair([3, 10, 5, 25, 2, 8])
print(f"Max XOR {xor_val} from pair ({a}, {b})")  # 28 from (5, 25)

4. Step-by-Step Example

Let us walk through a concrete example with the array nums = [3, 10, 5, 25, 2, 8]. In binary (using 5 bits for brevity): 3 = 00011, 10 = 01010, 5 = 00101, 25 = 11001, 2 = 00010, 8 = 01000. The expected maximum XOR is 28 from the pair 5 (00101) XOR 25 (11001) = 11100 (28).

We will trace the trie-based algorithm. We use max_bits = 4 (bits 4 down to 0) for this example. Initially, we insert 3 (00011) into an empty trie. The trie now has a single path: 0 -> 0 -> 0 -> 1 -> 1.

Next, we process 10 (01010). We query the trie containing only 3. Starting at bit 4: 10 has 0, we want 1 but the trie only has 0, so we go 0 (result bit 0). Bit 3: 10 has 1, we want 0, trie has 0, so we go 0 (result bit 1). Bit 2: 10 has 0, want 1, trie has 0, go 0 (result 0). Bit 1: 10 has 1, want 0, trie has 1, go 1 (result 0). Bit 0: 10 has 0, want 1, trie has 1, go 1 (result 1). The XOR found is 01001 = 9 (which is 10 XOR 3). We then insert 10, so the trie now branches.

We continue with 5 (00101). Querying against {3, 10}, the greedy search will try to diverge at the highest possible bit. For 5, the best partner in the current trie is 10, giving 15 (01111). After insertion, we process 25 (11001). This is the critical step. Querying 25 against {3, 10, 5}: Bit 4: 25 has 1, we want 0, and the trie has numbers with 0 at bit 4 (all previous numbers), so we take the 0 branch (result bit 1, value 16). Bit 3: 25 has 1, want 0, trie path 0->0 and 0->1 both exist, we can take 0 (result bit 1, value 24). Bit 2: 25 has 0, want 1, the remaining subtree under 0->0 has 1 at this position (from 5 = 00101), so we take 1 (result bit 1, value 28). Bits 1 and 0: we are forced to follow the only remaining path, which matches 5 exactly, giving no additional bits. The result is 11100 = 28, which becomes the new global maximum.

The remaining numbers 2 and 8 are processed similarly but do not exceed 28. For 2 (00010), the best partner is 25 giving 27, and for 8 (01000), the best is 25 giving 17. After all insertions, the algorithm correctly returns 28. This walkthrough highlights why processing from MSB to LSB is essential: the decision at bit 4 (value 16) outweighs all lower bits combined (max 15).

Visualizing the Trie After All Insertions

After inserting all six numbers, the trie has the following structure at the top levels: root branches to 0 (containing 3,10,5,2,8) and 1 (containing 25). The 0 subtree further branches on bit 3: 0->0 (3,5,2) and 0->1 (10,8). This hierarchical partitioning is what enables O(w) queries — at each level we make a single binary decision rather than scanning all numbers.

5. Complexity Analysis

Understanding the complexity of the maximum XOR pair algorithm is crucial for choosing the right implementation and predicting performance on large datasets. The analysis depends on two parameters: n, the number of elements in the array, and w, the bit width (typically 32 for 32-bit integers, or 60 for 64-bit integers).

The brute-force approach has O(n²) time complexity because it checks all n*(n-1)/2 pairs, each XOR operation being O(1). Its space complexity is O(1) auxiliary space. While simple, it becomes impractical when n exceeds a few thousand. For n = 100,000, it would require ~5 billion comparisons.

The trie-based optimized solution has O(n * w) time complexity. Each insertion takes O(w) steps (one per bit), and each query also takes O(w). With n insertions and n queries, total time is O(2 * n * w) = O(n * w). Since w is constant (32), this is effectively O(n) linear time. Space complexity is O(n * w) in the worst case, as each number may create up to w new nodes. However, many numbers share prefixes, so actual space is often less. In the worst case of all numbers being distinct and differing early, the trie will have n * w nodes.

The hash-set greedy approach has the same O(n * w) time complexity but different space characteristics. It iterates over w bits, and for each bit, it builds a set of n prefixes and scans them, leading to O(w * n) operations. Its auxiliary space is O(n) for the prefix set, which is more memory-efficient than the trie in practice, though it creates a new set each iteration.

Note that w = 32 for standard integers, so O(n * w) is often reported as O(n) or O(32n). For 64-bit integers, w = 64. The best, average, and worst cases are identical for the trie and hash-set methods because the work per number is always proportional to w, regardless of input distribution. This contrasts with comparison-based algorithms like quicksort, where input order affects performance.

Impact of Bit Width

If the input numbers are small (e.g., all < 1024, so only 10 bits needed), we can optimize by dynamically computing max_bits = max(nums).bit_length(). This reduces w from 32 to 10, giving a 3x speedup. However, for asymptotic analysis, w is still considered constant.

6. Variations and Optimizations

The basic maximum XOR pair problem has several important variations that appear in interviews and production systems. Understanding these extensions demonstrates deeper mastery of bit manipulation.

The first major variation is the Maximum XOR Query problem, where we are given a static array and many queries of the form: given x, find max(x XOR a) for a in the array. The solution is to build the trie once in O(n * w) and answer each query in O(w), making it ideal for online systems. If queries arrive interleaved with insertions, the trie supports dynamic updates efficiently.

A second variation is Maximum XOR Subarray, where we seek a contiguous subarray whose XOR is maximized. This reduces to the maximum XOR pair problem on prefix XORs. If we compute prefix[0] = 0 and prefix[i] = arr[0] XOR arr[1] XOR ... XOR arr[i-1], then the XOR of subarray [l, r] equals prefix[r+1] XOR prefix[l]. Thus, finding the maximum subarray XOR is equivalent to finding the maximum XOR pair among prefix values, solvable with the same trie in O(n * w).

A third variation is K Maximum XOR Pairs, which asks for the top k pairs with highest XOR. This can be solved by combining the trie with a max-heap. For each number, we can find its best partner, push the result into a heap, and then iteratively explore next-best partners by branching in the trie. Complexity becomes O((n + k) * w + k log n).

Optimization Techniques

Several low-level optimizations improve constant factors. Array-based trie replaces pointer-based nodes with a 2D array trie[node][0/1] = child_index and a list for node count. This improves cache locality and reduces Python object overhead, often yielding 2-3x speedups. Bit-length pruning computes the actual maximum bit needed instead of always using 31. Early termination can stop a query early if the remaining bits cannot possibly beat the current global maximum, though this rarely helps in practice.

For very large datasets that do not fit in memory, external memory or distributed variants partition the trie across machines. Each machine holds a subtree, and queries are routed accordingly. Another optimization for repeated queries is to compress the trie into a binary radix tree, merging chains of single-child nodes, which reduces depth and memory.

Handling Negative Numbers

In languages like Python, integers have arbitrary precision and negative numbers are represented with infinite leading ones in two's complement. To handle negatives correctly, we should treat numbers as fixed-width (e.g., 32-bit) by masking: num & 0xFFFFFFFF or by using max_bits = 31 and handling the sign bit specially. Alternatively, we can offset all numbers by + 2^31 to make them non-negative while preserving XOR ordering.

7. Real-World Applications

While the maximum XOR pair algorithm is often taught as an interview puzzle, its underlying principles power several real-world systems, particularly where binary representations and Hamming distance matter.

In networking and IP routing, longest prefix match — the core operation of routers forwarding packets — uses a binary trie nearly identical to the XOR trie. An IP address is matched against a routing table to find the most specific prefix. The same trie structure that helps find maximum XOR also enables O(w) routing lookups. Some load balancers use XOR-based hashing to distribute traffic, and finding pairs with maximum XOR can help identify the most diverse hash buckets.

In cryptography and error detection, XOR is fundamental. The maximum XOR pair concept relates to finding codewords with maximum Hamming distance, which is desirable for error-correcting codes. In differential cryptanalysis, analysts search for input pairs that maximize XOR differences to find weaknesses in ciphers. While not directly using the maximum XOR pair algorithm, the bit-greedy mindset is central.

In databases and similarity search, binary embeddings are used for approximate nearest neighbor search. For example, locality-sensitive hashing (LSH) maps high-dimensional vectors to binary codes, and finding the most dissimilar pair (maximum Hamming distance, which correlates with maximum XOR for binary codes) helps with diversity sampling and outlier detection. Web servers and databases also use XOR-based checksums and consistent hashing, where understanding XOR distribution is useful.

In machine learning and data mining, feature selection sometimes involves finding the most discriminative binary features. If features are binarized, the pair with maximum XOR represents the most complementary features. In genetic algorithms, chromosomes are often binary strings, and crossover operations benefit from pairing individuals with high Hamming distance to maintain population diversity.

A notable example is the Kademlia distributed hash table used in BitTorrent and Ethereum. Kademlia defines distance between nodes as XOR of their IDs, and the routing table is organized as a binary trie (called k-buckets) where each subtree corresponds to a prefix. Finding the k closest nodes to a target is essentially a k-nearest XOR query, directly leveraging the trie structure from the maximum XOR algorithm.

8. Comparison with Alternatives

Choosing the right approach for maximum XOR depends on constraints like input size, memory limits, and whether you need just the value or the actual pair. Below is a comprehensive comparison of the main alternatives.

The sorting heuristic deserves special mention because it is a common trap. A naive idea is to sort the array and check neighboring elements or extremes, assuming large XOR comes from numerically distant numbers. This fails because XOR is not correlated with numeric distance. For example, 8 (1000) and 7 (0111) are numerically close (difference 1) but give maximum XOR 15 (1111), while 8 (1000) and 9 (1001) are also close but give small XOR 1. Sorting works for maximum difference or maximum product, but not for XOR.

Between the two optimal methods, the trie is more versatile: it naturally supports retrieving the partner element, handling streaming data, and answering many queries after one build. The hash-set method is slightly faster and more memory-efficient in Python when only the maximum value is needed, because it avoids creating many small objects. For production code with n > 10^5, an array-based trie (using lists of size [nodes][2]) is often the best compromise, giving trie versatility with near hash-set speed.

When to Use Which

Use brute force only for verification or when n < 500. Use hash-set greedy for one-off maximum value computation in interviews where brevity matters. Use binary trie for any scenario requiring the actual pair, dynamic data, or repeated queries. If memory is extremely tight and you can tolerate rebuilding, hash-set is preferable.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing the maximum XOR pair algorithm. Recognizing these pitfalls early saves hours of debugging.

Mistake 1: Incorrect Bit Width and Sign Handling. Using range(31, -1, -1) is correct for non-negative 32-bit integers, but if the input can contain negative numbers or numbers up to 10^18, this truncates high bits. Always compute max_bits = max(max(nums).bit_length(), 1) - 1 or use a fixed 31/63 based on problem constraints. For negatives in Python, mask with (1 << 32) - 1 to simulate 32-bit two's complement, or shift to non-negative range.

Mistake 2: Forgetting to Escape or Misusing Bit Shifts. In Python, 1 << i can create very large integers if i is large, but more commonly, developers confuse >> (right shift) with << (left shift) when extracting bits. The correct extraction is (num >> i) & 1, not (num << i) & 1. Also, when building the answer, use ans | (1 << i) to set a bit, not ans ^ (1 << i) which toggles.

Mistake 3: Querying Before Inserting vs. After. If you insert all numbers first and then query, you may pair a number with itself, which is allowed in some problem variants but not in others. The standard LeetCode 421 problem allows i != j but numbers can be equal, so pairing a number with itself is only an issue if duplicates exist and you insert-then-query without care. The safe pattern is: insert first element, then for each next element, query then insert. This guarantees i < j and avoids self-pairing.

Mistake 4: Trie Node Initialization Errors. A common bug is sharing the same children list across nodes by using a mutable default argument or class variable. Always initialize self.children = [None, None] inside __init__. Another bug is not handling the case where a child is None during query — you must check existence before traversing.

Best Practice 1: Use Iterative Bit Loops, Not Recursion. Recursive trie insertion/query risks hitting Python's recursion limit for w=32 (though 32 is safe, deeper tries for 64-bit are still okay, but iterative is faster and clearer). Stick to for i in range(max_bits, -1, -1).

Best Practice 2: Validate with Brute Force on Small Random Tests. Always test your optimized solution against brute force for hundreds of random small arrays (e.g., n=20, values 0-100). This catches off-by-one errors in bit width and greedy logic. Use a simple assert loop during development.

Best Practice 3: Consider Array-Based Trie for Performance. In Python, object-based tries are slow for n > 50000. An array-based implementation using children = [[-1, -1]] and next_index = 1 is significantly faster and more memory-efficient. Pre-allocate if possible.

Best Practice 4: Document Assumptions. Clearly state whether your function assumes non-negative integers, 32-bit range, or handles duplicates. This prevents misuse in larger systems where input constraints may change.

10. Interview Questions

The maximum XOR pair algorithm is a favorite in technical interviews because it tests bit manipulation, trie knowledge, and greedy reasoning. Here are common questions and how to approach them.

Q1: Find the Maximum XOR of Two Numbers in an Array (LeetCode 421)

Problem: Given an integer array nums, return the maximum result of nums[i] XOR nums[j] where i != j.

Approach: This is the direct application. Discuss the brute-force O(n²) baseline, then present the trie solution in O(n * 32). Interviewers expect you to explain why greedy works (higher bits dominate) and to code the trie insertion and query. Mention the hash-set alternative as a follow-up. Complexity: O(n) time, O(n) space. Edge cases: array length < 2, all zeros, duplicates.

Q2: Maximum XOR With an Element From Array (LeetCode 1707)

Problem: You are given an array nums and queries queries[i] = [xi, mi]. For each query, find the maximum XOR with xi using only elements in nums that are <= mi.

Approach: This tests offline processing. Sort nums and sort queries by mi. Iterate queries in increasing mi, inserting into the trie all nums elements <= current mi, then query for xi. This avoids rebuilding the trie per query. Complexity: O((n + q) * w + (n+q) log(n+q)) for sorting. The key insight is incremental trie building sorted by constraint.

Q3: Maximum XOR Subarray

Problem: Find the maximum XOR value of any contiguous subarray.

Approach: Reduce to maximum XOR pair on prefix XORs. Compute prefix[0]=0, prefix[i+1]=prefix[i] XOR arr[i]. The XOR of subarray [l..r] is prefix[r+1] XOR prefix[l]. So the problem becomes finding the maximum XOR pair among prefix array, solvable with the same trie. This tests ability to transform problems. Complexity: O(n * w) time, O(n * w) space. Follow-up: also return the subarray indices by storing prefix indices in trie leaves.

Q4: Find the Pair with Maximum XOR and Count Such Pairs

Problem: Given an array, find the maximum XOR value and count how many pairs achieve it.

Approach: First find max_xor using the trie. Then count pairs. Naive counting is O(n²), but we can do better: for each number, query the trie to find how many partners give max_xor. This requires a trie that counts occurrences per subtree. During query, if both branches could lead to max_xor, we need to explore both. Simpler is to use a hash map of frequencies and for each num, check if num ^ max_xor exists, summing frequencies. Complexity: O(n * w) for max, plus O(n) for counting with hash map.

Q5: Minimum XOR Pair — What Changes?

Problem: Find the pair with minimum XOR value (closest numbers in XOR metric).

Approach: The trie still works, but the greedy strategy flips: at each bit, prefer the same branch (to keep result bit 0) instead of the opposite. However, unlike maximum XOR, sorting helps here: the minimum XOR pair must be among adjacent elements in sorted order. Proof sketch: if a < b < c in sorted order, then a XOR c >= min(a XOR b, b XOR c) is not always true for XOR, but empirically the minimum XOR pair is often close in sorted order, and a proven O(n log n) solution is to sort and check adjacent pairs. Discuss both approaches and their trade-offs: trie gives O(n * w) exact, sorting adjacent check gives O(n log n) but is also exact for minimum XOR (unlike maximum). This question tests deep understanding of when greedy preferences invert.

Preparing for these questions involves not just memorizing code, but being able to derive the greedy proof, analyze complexity, and adapt the trie to new constraints. Practice implementing both the object-based and array-based trie, and always be ready to discuss the hash-set alternative.