Problem Types - Learning Module

Loading content...

0/276

Maximum XOR Pair

Finding Maximum Difference in Binary

Given an array of integers, find two numbers whose XOR is maximum. This problem elegantly combines bit manipulation with data structures, requiring us to think about numbers as sequences of bits and leverage the trie data structure in an unexpected way.

The Maximum XOR Pair problem appears in competitive programming, coding interviews, and has practical applications in network routing (finding maximum prefix differences), cryptographic analysis, and optimization algorithms.

The Challenge:

Input:  [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: Maximum XOR is between 5 (00101) and 25 (11001)
             5 ⊕ 25 = 00101 ⊕ 11001 = 11100 = 28

The brute force approach checks all pairs in O(n²). Can we do better?

What You Will Master

By the end of this page, you will understand the bit-by-bit greedy strategy for maximizing XOR, implement a trie (prefix tree) tailored for binary numbers, achieve O(n × L) time complexity (where L is bit length), and recognize variations of this problem pattern.

Understanding Maximum XOR

To maximize XOR, we need to understand what makes one XOR result larger than another.

Key insight: XOR produces 1 when bits differ. To maximize the result, we want the most significant bits to differ as much as possible.

Example analysis:

7 ⊕ 8 = 0111 ⊕ 1000 = 1111 = 15
7 ⊕ 6 = 0111 ⊕ 0110 = 0001 = 1

Why is 7 ⊕ 8 = 15 so much larger? Because the MSB differs (0 vs 1), immediately giving us a 1 in the highest position. In contrast, 7 and 6 share the same MSB, so their XOR starts with 0.

Maximizing XOR: The Greedy Strategy

•Start from the MSB: A difference in bit 31 contributes 2³¹, dwarfing all other bits combined
•Greedily seek opposites: For each bit position, if we can find a number with the opposite bit, choose it
•Process bit by bit: This greedy approach works because higher bits dominate lower bits
•Build the result progressively: Each bit decision is locally optimal and globally optimal

Bit Position Values (32-bit)
Bit Position	Value	Cumulative of Lower Bits
Bit 31 (MSB)	2,147,483,648	—
Bit 30	1,073,741,824	Sum of bits 0-29: 1,073,741,823
Bit 29	536,870,912	Sum of bits 0-28: 536,870,911
Bit 7	128	Sum of bits 0-6: 127
Bit 3	8	Sum of bits 0-2: 7
Bit 0 (LSB)	1	—

The Dominance of Higher Bits

Notice that each bit position is worth more than all lower bits combined! This is why the greedy strategy works: getting a 1 in a higher position is always better than any combination of 1s in lower positions. A 1 in bit position k is worth 2^k, while all lower bits sum to 2^k - 1.

Brute Force: Checking All Pairs

The straightforward approach is to compute XOR for every pair and track the maximum. This establishes our baseline before optimization.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function maxXorBruteForce(nums: number[]): number {
    const n = nums.length;
    if (n < 2) return 0;
    
    let maxXor = 0;
    let bestPair: [number, number] = [0, 0];
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const xorValue = nums[i] ^ nums[j];
            if (xorValue > maxXor) {
                maxXor = xorValue;
                bestPair = [nums[i], nums[j]];
            }
        }
    }
    
    console.log(`Best pair: ${bestPair[0]} ⊕ ${bestPair[1]} = ${maxXor}`);
    return maxXor;
}
 
// Test
const nums = [3, 10, 5, 25, 2, 8];
console.log(maxXorBruteForce(nums));
// Output: Best pair: 5 ⊕ 25 = 28
// Returns: 28
 
// Let's verify all pairs for this small example:
// 3 ⊕ 10 = 9,   3 ⊕ 5 = 6,   3 ⊕ 25 = 26,  3 ⊕ 2 = 1,   3 ⊕ 8 = 11
// 10 ⊕ 5 = 15, 10 ⊕ 25 = 19, 10 ⊕ 2 = 8,   10 ⊕ 8 = 2
// 5 ⊕ 25 = 28, 5 ⊕ 2 = 7,    5 ⊕ 8 = 13
// 25 ⊕ 2 = 27, 25 ⊕ 8 = 17
// 2 ⊕ 8 = 10
//
// Maximum is 5 ⊕ 25 = 28 ✓
 
// Time complexity: O(n²)
// Space complexity: O(1)

Why O(n²) is problematic:

For n = 100,000, we'd compute 5 billion pairs. Even at 10 million operations per second, this takes 500 seconds. We need a smarter approach.

The key observation:

Instead of comparing every pair, what if we could, for each number, quickly find the number that would maximize its XOR? If we could do this in O(L) time where L is the bit length (e.g., 32), we'd have an O(n × L) = O(n) solution!

The Search Problem

Given a number x, we want to find the number y in our set such that x ⊕ y is maximized. This means at each bit position, we want y's bit to be different from x's bit. We're searching for the 'most opposite' number!

The Binary Trie: A Perfect Data Structure

A trie (prefix tree) is a tree structure where each path from root to leaf represents a sequence. Typically used for strings, we'll use it for binary representations of numbers.

Binary Trie Structure:

Each node has at most two children: one for bit '0', one for bit '1'
Numbers are inserted from MSB to LSB
Each path represents a number's binary representation
Multiple numbers share common prefixes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class TrieNode {
    children: [TrieNode | null, TrieNode | null];  // [0-child, 1-child]
    
    constructor() {
        this.children = [null, null];
    }
}
 
class BinaryTrie {
    root: TrieNode;
    maxBits: number;
    
    constructor(maxBits: number = 31) {
        this.root = new TrieNode();
        this.maxBits = maxBits;  // Number of bits to consider
    }
    
    /**
     * Insert a number into the trie
     * Process from MSB to LSB
     */
    insert(num: number): void {
        let node = this.root;
        
        // Process each bit from MSB (maxBits-1) down to LSB (0)
        for (let i = this.maxBits - 1; i >= 0; i--) {
            const bit = (num >>> i) & 1;  // Extract bit at position i
            
            // Create child node if it doesn't exist
            if (node.children[bit] === null) {
                node.children[bit] = new TrieNode();
            }
            
            node = node.children[bit]!;
        }
    }
    
    /**
     * Find the maximum XOR of 'num' with any number in the trie
     * Greedily choose the opposite bit at each level
     */
    findMaxXor(num: number): number {
        let node = this.root;
        let maxXor = 0;
        
        for (let i = this.maxBits - 1; i >= 0; i--) {
            const bit = (num >>> i) & 1;
            const oppositeBit = 1 - bit;  // The bit we'd prefer
            
            // If we can go opposite, do so (maximizes XOR at this position)
            if (node.children[oppositeBit] !== null) {
                maxXor |= (1 << i);  // This bit will be 1 in the XOR result
                node = node.children[oppositeBit]!;
            } else if (node.children[bit] !== null) {
                // Otherwise, go same (XOR bit will be 0)
                node = node.children[bit]!;
            } else {
                // Shouldn't happen if trie has at least one number
                break;
            }
        }
        
        return maxXor;
    }
}
 
// Visualization of the trie for [3, 10, 5, 25, 2, 8] with 5 bits:
//
//  3 = 00011,  10 = 01010,  5 = 00101
// 25 = 11001,   2 = 00010,  8 = 01000
//
//                   root
//                  /    \
//                 0      1
//                / \      \
//               0   1      1
//              /   /        \
//             0   0          0
//            / \  |          |
//           0   1  1          0
//          /   / \  \         |
//         N   0   1  0        1
//            (2) (3)(10)     (25)
//             5 is at 00101
//             8 is at 01000

Why Trie Works for Maximum XOR

The trie encodes all numbers by their bit patterns. To find the maximum XOR for a query number, we traverse the trie from root to leaf, always preferring the child that gives the opposite bit. This greedy choice is optimal because higher bits dominate lower bits in determining the XOR value.

Complete Solution: O(n × L) Algorithm

Now we combine insertion and querying to solve the maximum XOR pair problem efficiently.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class TrieNode {
    children: [TrieNode | null, TrieNode | null] = [null, null];
}
 
function findMaximumXOR(nums: number[]): number {
    if (nums.length < 2) return 0;
    
    // Determine the maximum number of bits needed
    const maxNum = Math.max(...nums);
    const maxBits = maxNum > 0 ? Math.floor(Math.log2(maxNum)) + 1 : 1;
    
    const root = new TrieNode();
    let maxXor = 0;
    
    // Insert first number
    insertIntoTrie(root, nums[0], maxBits);
    
    // For each subsequent number, find max XOR with existing numbers
    for (let i = 1; i < nums.length; i++) {
        // Query before insert: find best match among previously inserted numbers
        const currentMaxXor = queryMaxXor(root, nums[i], maxBits);
        maxXor = Math.max(maxXor, currentMaxXor);
        
        // Insert current number for future queries
        insertIntoTrie(root, nums[i], maxBits);
    }
    
    return maxXor;
}
 
function insertIntoTrie(root: TrieNode, num: number, maxBits: number): void {
    let node = root;
    for (let i = maxBits - 1; i >= 0; i--) {
        const bit = (num >>> i) & 1;
        if (node.children[bit] === null) {
            node.children[bit] = new TrieNode();
        }
        node = node.children[bit]!;
    }
}
 
function queryMaxXor(root: TrieNode, num: number, maxBits: number): number {
    let node = root;
    let maxXor = 0;
    
    for (let i = maxBits - 1; i >= 0; i--) {
        const bit = (num >>> i) & 1;
        const oppositeBit = 1 - bit;
        
        if (node.children[oppositeBit] !== null) {
            maxXor |= (1 << i);
            node = node.children[oppositeBit]!;
        } else {
            node = node.children[bit]!;
        }
    }
    
    return maxXor;
}
 
// Test cases
console.log(findMaximumXOR([3, 10, 5, 25, 2, 8]));  // 28 (5 ⊕ 25)
console.log(findMaximumXOR([14, 70, 53, 83, 49])); // 127 (83 ⊕ 53 = 127)
console.log(findMaximumXOR([1, 2, 3, 4, 5]));       // 7 (3 ⊕ 4 = 7)
console.log(findMaximumXOR([8, 1, 2, 12, 7, 6]));  // 15 (8 ⊕ 7 = 15)
 
// Trace for [3, 10, 5, 25, 2, 8]:
// After inserting 3:  trie has path 00011
// Query with 10 (01010): best opposite is 00011, gives 01010 ⊕ 00011 = 01001 = 9
//   → maxXor = 9
// 
// After inserting 10: trie has 00011, 01010
// Query with 5 (00101): best paths give 5 ⊕ 3 = 6 or 5 ⊕ 10 = 15
//   → maxXor = 15
//
// After inserting 5: trie has 00011, 01010, 00101  
// Query with 25 (11001): greedily goes to 00--- for opposite MSB
//   best is 5: 11001 ⊕ 00101 = 11100 = 28
//   → maxXor = 28
//
// Continue for 2 and 8, but 28 remains maximum

Complexity Analysis:

Metric	Value	Explanation
Time	O(n × L)	n insertions and n queries, each O(L)
Space	O(n × L)	At most n paths of length L in trie
Where L	31 or 32	Number of bits for 32-bit integers
Effective	O(n)	L is constant for fixed-width integers

This is a dramatic improvement over O(n²)!

Insert-Then-Query vs Query-Then-Insert

We insert the first number, then for each subsequent number:

Query (find max XOR with existing numbers)
Insert (add current number for future queries)

This ensures we consider all pairs exactly once without pairing a number with itself.

Alternative Approach: Hash Set Optimization

An elegant alternative uses a hash set with bit-by-bit construction. The idea: greedily build the answer from MSB to LSB, checking if each bit can be achieved.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
function findMaximumXORHashSet(nums: number[]): number {
    let maxXor = 0;
    let mask = 0;
    
    // Process from MSB to LSB
    for (let i = 30; i >= 0; i--) {
        // Add current bit to mask
        mask |= (1 << i);
        
        // Create set of all prefixes up to current bit
        const prefixes = new Set<number>();
        for (const num of nums) {
            prefixes.add(num & mask);
        }
        
        // Greedily try to set this bit in answer
        const candidate = maxXor | (1 << i);
        
        // Check if any two prefixes XOR to candidate
        // If a ⊕ b = candidate, then a ⊕ candidate = b
        for (const prefix of prefixes) {
            if (prefixes.has(prefix ^ candidate)) {
                maxXor = candidate;  // This bit CAN be achieved!
                break;
            }
        }
        // If no pair found, this bit stays 0 in maxXor
    }
    
    return maxXor;
}
 
// The key insight:
// If we want to check if XOR result can have bit i set (while keeping 
// higher bits we've already determined), we check if there exist two
// numbers whose prefixes (bits from MSB to bit i) XOR to our candidate.
//
// Using the property: if a ⊕ b = c, then a ⊕ c = b
// So we iterate through prefixes and check if prefix ⊕ candidate exists.
 
console.log(findMaximumXORHashSet([3, 10, 5, 25, 2, 8]));  // 28
 
// Trace:
// i=4 (bit 16): mask=10000, prefixes={00000,01010,00000,11000,00000,00000}
//               = {0, 8, 24} after dedup for 5 bits
//               candidate = 10000 (16)
//               Check: 0⊕16=16? No. 8⊕16=24? Yes! 
//               maxXor = 16
//
// i=3 (bit 8):  mask=11000, candidate = 11000 (24)
//               Check prefixes... 0⊕24=24? Yes!
//               maxXor = 24
//
// i=2 (bit 4):  mask=11100, candidate = 11100 (28)
//               Check if achievable... Yes (5 prefix ⊕ 25 prefix)
//               maxXor = 28
//
// i=1,0: Check bits 1 and 0, but 28 already max achievable
// Final: 28

Trie vs Hash Set Approach
Aspect	Trie Approach	Hash Set Approach
Time Complexity	O(n × L)	O(n × L)
Space Complexity	O(n × L)	O(n)
Implementation	More complex (tree)	Simpler (set + loop)
Constants	Lower (single pass)	Higher (L passes over array)
Variants	Easy to extend	Harder to modify

When to Use Which

The hash set approach is more elegant and uses less space. The trie approach is more flexible—it's easier to extend for problems like "maximum XOR with a number less than K" or handling streaming data where numbers arrive over time.

Variations and Extensions

The maximum XOR pair problem has several important variations that appear in interviews and competitions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Given an array and a number x, find the maximum XOR of x with any array element
 
class BinaryTrieWithQuery {
    root: TrieNode = new TrieNode();
    maxBits: number;
    
    constructor(nums: number[], maxBits: number = 30) {
        this.maxBits = maxBits;
        for (const num of nums) {
            this.insert(num);
        }
    }
    
    insert(num: number): void {
        let node = this.root;
        for (let i = this.maxBits; i >= 0; i--) {
            const bit = (num >>> i) & 1;
            if (!node.children[bit]) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit]!;
        }
    }
    
    maxXorWith(x: number): number {
        let node = this.root;
        let result = 0;
        
        for (let i = this.maxBits; i >= 0; i--) {
            const bit = (x >>> i) & 1;
            const opposite = 1 - bit;
            
            if (node.children[opposite]) {
                result |= (1 << i);
                node = node.children[opposite]!;
            } else if (node.children[bit]) {
                node = node.children[bit]!;
            } else {
                break;
            }
        }
        
        return result;
    }
}
 
// Usage:
const trie = new BinaryTrieWithQuery([3, 10, 5, 25, 2, 8]);
console.log(trie.maxXorWith(7));   // Maximum XOR of 7 with array elements
console.log(trie.maxXorWith(0));   // Maximum element in array (XOR with 0)
console.log(trie.maxXorWith(31));  // 31 XOR with optimal array element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Find the maximum XOR of any contiguous subarray
// Key insight: XOR of subarray[l...r] = prefix[r] ⊕ prefix[l-1]
// So this reduces to finding max XOR pair in prefix XOR array!
 
function maxXorSubarray(nums: number[]): number {
    const n = nums.length;
    
    // Compute prefix XOR array
    const prefixXor: number[] = [0];  // prefix[0] = 0 (empty prefix)
    let xor = 0;
    for (const num of nums) {
        xor ^= num;
        prefixXor.push(xor);
    }
    
    // Now find max XOR pair in prefixXor
    // prefixXor has n+1 elements
    return findMaximumXOR(prefixXor);
}
 
console.log(maxXorSubarray([1, 2, 3, 4]));
// Prefix XOR: [0, 1, 3, 0, 4]
// Max pair: 3 ⊕ 4 = 7, or other pairs
// This represents subarray ending at that prefix
 
console.log(maxXorSubarray([8, 1, 2, 12]));
// Explore to find maximum XOR contiguous subarray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Find maximum XOR pair where both numbers are <= limit
// Requires trie that stores the actual number value at leaves
 
class TrieNodeWithValue {
    children: [TrieNodeWithValue | null, TrieNodeWithValue | null] = [null, null];
    value: number | null = null;  // Store number at leaf
}
 
function maxXorWithLimit(nums: number[], limit: number): number {
    // Filter numbers within limit first
    const validNums = nums.filter(n => n <= limit);
    
    if (validNums.length < 2) return 0;
    
    // Use standard algorithm on filtered array
    return findMaximumXOR(validNums);
}
 
// More complex variation: One number <= limit, other can be anything
// Requires modified trie traversal with limit checking

Other Important Variations

•K Maximum XOR Pairs: Find the k largest XOR values, not just the maximum
•Minimum XOR Pair: Similar approach but choose same bit when possible
•XOR Queries: Answer multiple "max XOR with x" queries efficiently
•Persistent Trie: For range queries "max XOR in array[l..r] with x"
•Online Maximum XOR: Handle insert and query operations interleaved

Real-World Applications

The maximum XOR pair algorithm and its variations have practical applications beyond competitive programming.

Practical Applications

•IP Routing: Finding the longest prefix match in routing tables uses similar trie structures with bits representing IP octets
•Error Detection: Maximizing XOR difference helps identify bit positions most prone to error in communication channels
•Cryptographic Analysis: Finding maximum XOR pairs can reveal weaknesses in XOR-based encryption
•Data Deduplication: Identifying most different items in a dataset for representative sampling
•Network Topology: Finding most dissimilar nodes in P2P networks for optimal distribution

Interview Context

Maximum XOR pair is a popular interview question because it:

Tests knowledge of bit manipulation fundamentals
Requires creative use of data structures (trie)
Has a non-obvious O(n) solution
Can be solved multiple ways (trie or hash set)
Has natural follow-up questions (variations)

Being able to explain the greedy insight and trie structure demonstrates deep understanding.

Summary: Maximum XOR Mastered

We've thoroughly explored the maximum XOR pair problem and its deep connection between bit manipulation and data structures.

Key Takeaways

•High bits dominate: Each bit position is worth more than all lower bits combined, enabling greedy optimization
•Binary trie is perfect: The trie structure maps directly to bit-by-bit decision making
•Greedy works: At each bit, choosing the opposite maximizes that position's contribution
•O(n × L) is optimal: Where L is constant (32 bits), this is effectively O(n) linear time
•Hash set alternative: Can achieve same complexity with simpler code and less space
•Many variations exist: Subarray XOR, range queries, k-maximum, and online versions
•Real applications: IP routing, error detection, cryptography all use similar techniques

Algorithm Summary:

// Trie Approach
1. Build a binary trie of all numbers
2. For each number, greedily traverse trie choosing opposite bits
3. Track maximum XOR found

// Hash Set Approach  
1. Process bit by bit from MSB to LSB
2. For each bit, check if it can be set in the answer
3. Use hash set to verify pair existence

What's next:

Our final topic in bit manipulation problem types is Gray Code—a binary numeral system where consecutive values differ in exactly one bit. This elegant sequence has fascinating properties and practical applications in error correction, analog-to-digital conversion, and solving the Towers of Hanoi!

Page Complete

You now understand how to find maximum XOR pairs efficiently using tries. This problem beautifully demonstrates how the right data structure—chosen to match the problem's structure—transforms an O(n²) problem into an O(n) one. The greedy bit-by-bit insight is broadly applicable to many bit manipulation problems.