163. Maximum XOR of Two Numbers in an Array

🔗 LeetCode Problem: 421. Maximum XOR of Two Numbers in an Array
📊 Difficulty: Medium
🏷️ Topics: Trie, Bit Manipulation, Array, Binary Trie

Problem Statement

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints: - 1 <= nums.length <= 2 * 10^5 - 0 <= nums[i] <= 2^31 - 1

---

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving:

Given: nums = [3, 10, 5, 25, 2, 8]
Find: Maximum XOR of ANY TWO numbers

Question: Which PAIR gives maximum XOR?
  3 XOR 10 = ?
  3 XOR 5 = ?
  5 XOR 25 = ?
  ... all possible pairs?

We DON'T KNOW which pair is best! 🤔

Why We Must Check Every Number:

CRITICAL UNDERSTANDING:

We must find the best XOR partner for EACH number!

For number 3:
  3 XOR 3  = 0
  3 XOR 10 = 9
  3 XOR 5  = 6
  3 XOR 25 = 26
  3 XOR 2  = 1
  3 XOR 8  = 11
  Best for 3: 26 (with 25)

For number 10:
  10 XOR 3  = 9
  10 XOR 10 = 0
  10 XOR 5  = 15
  10 XOR 25 = 19
  10 XOR 2  = 8
  10 XOR 8  = 2
  Best for 10: 19 (with 25)

For number 5:
  5 XOR 3  = 6
  5 XOR 10 = 15
  5 XOR 5  = 0
  5 XOR 25 = 28  ← MAXIMUM!
  5 XOR 2  = 7
  5 XOR 8  = 13
  Best for 5: 28 (with 25)

For number 25:
  25 XOR 3  = 26
  25 XOR 10 = 19
  25 XOR 5  = 28  ← SAME PAIR!
  25 XOR 25 = 0
  25 XOR 2  = 27
  25 XOR 8  = 17
  Best for 25: 28 (with 5)

For number 2:
  2 XOR 3  = 1
  2 XOR 10 = 8
  2 XOR 5  = 7
  2 XOR 25 = 27
  2 XOR 2  = 0
  2 XOR 8  = 10
  Best for 2: 27 (with 25)

For number 8:
  8 XOR 3  = 11
  8 XOR 10 = 2
  8 XOR 5  = 13
  8 XOR 25 = 17
  8 XOR 2  = 10
  8 XOR 8  = 0
  Best for 8: 17 (with 25)

GLOBAL MAXIMUM = max(26, 19, 28, 28, 27, 17) = 28 ✓

The winning pair: 5 XOR 25 = 28
(We find it when processing either 5 or 25)

WE MUST CHECK EVERY NUMBER! 🔑

The Algorithm Flow:

STEP 1: Build Trie with ALL numbers
  insert(3)   → Trie has: [3]
  insert(10)  → Trie has: [3, 10]
  insert(5)   → Trie has: [3, 10, 5]
  insert(25)  → Trie has: [3, 10, 5, 25]
  insert(2)   → Trie has: [3, 10, 5, 25, 2]
  insert(8)   → Trie has: [3, 10, 5, 25, 2, 8]

STEP 2: For EACH number, find best partner using Trie
  maxXOR = 0

  Process 3:  best = 26 → maxXOR = 26
  Process 10: best = 19 → maxXOR = 26
  Process 5:  best = 28 → maxXOR = 28 ✓
  Process 25: best = 28 → maxXOR = 28
  Process 2:  best = 27 → maxXOR = 28
  Process 8:  best = 17 → maxXOR = 28

STEP 3: Return maxXOR = 28

This is why we check EVERY number! 🎯

From String Trie to Binary Trie:

Problems 161/162: String Trie
  - 26 children (a-z)
  - Characters on edges
  - Word matching

Problem 163: Binary Trie
  - 2 children (0, 1)
  - Bits on edges
  - Number matching

SAME structure, DIFFERENT alphabet! 🎯

XOR Refresher:

XOR Truth Table:
  0 XOR 0 = 0
  0 XOR 1 = 1 ✓
  1 XOR 0 = 1 ✓
  1 XOR 1 = 0

KEY INSIGHT: XOR is maximized when bits are DIFFERENT! 🔑

Example:
  5  = 0101
  3  = 0011
  ────────────
  XOR = 0110 = 6

  5  = 0101
  25 = 11001
  ────────────
  XOR = 11100 = 28 (much larger!)

Why? More DIFFERENT bits = larger XOR!

---

🧠 The AHA Moment - Why Trie Solves This

The Brute Force Problem:

To find max XOR, we check every number:

For number 3:
  Try: 3 XOR 3, 3 XOR 10, 3 XOR 5, 3 XOR 25, ...
  Time: O(n) to check all partners

For number 10:
  Try: 10 XOR 3, 10 XOR 10, 10 XOR 5, 10 XOR 25, ...
  Time: O(n) to check all partners

... for all n numbers

Total Time: O(n²) - TOO SLOW! 😰

How Trie Helps:

INSIGHT: Instead of checking ALL numbers,
         use Trie to find the BEST partner directly!

Trie organizes all numbers by their bit patterns:

                    root
                   /    \
              [0]          [1]
               |            |
        (3,10,5,2,8)       (25)

This structure shows us:
  - Which numbers start with 0 (left branch)
  - Which numbers start with 1 (right branch)

When finding best partner for ANY number:
  - Look at current bit
  - Want opposite bit? Check if that branch exists!
  - Trie answers this in O(1)!

Instead of O(n) to check all numbers,
we navigate Trie in O(32) = O(1)!

Total: O(n) instead of O(n²)! 🚀

The Greedy Strategy (Works for ANY Number):

For ANY number, to maximize XOR:
  - Process bits from MSB to LSB (left to right)
  - At each bit position, want OPPOSITE bit
  - Check Trie: Is opposite bit available?
    - YES → Take it! (maximizes this bit)
    - NO → Must take same bit (no choice)

Why greedy works:
  Bit values: [16, 8, 4, 2, 1] (for 5 bits)
  Bit 4 (16) > all other bits combined (15)!

  So ALWAYS maximize leftmost bits first!
  Greedy = Optimal! 🔑

Example: Finding Best Partner for 5

5 = 00101

Step-by-step using Trie:

BIT 4 (value 16 - MOST IMPORTANT):
  5 has: 0
  Want:  1

  Check Trie at root:
    children[0]: exists (has 3,10,5,2,8)
    children[1]: exists (has 25) ✓

  Decision: Go to children[1]!
  XOR so far: 10000 = 16
  Following path to: 25

BIT 3 (value 8):
  5 has: 0
  Want:  1

  Check current node (in "1" branch):
    children[0]: no
    children[1]: yes (25) ✓

  Decision: Go to children[1]!
  XOR so far: 11000 = 24
  Still on path to: 25

BIT 2 (value 4):
  5 has: 1
  Want:  0

  Check current node:
    children[0]: yes (25) ✓
    children[1]: no

  Decision: Go to children[0]!
  XOR so far: 11100 = 28
  Still on path to: 25

BIT 1 (value 2):
  5 has: 0
  Want:  1

  Check current node:
    children[0]: yes (25)
    children[1]: no ✗

  Decision: Must take children[0] (no choice)
  XOR so far: 11100 = 28 (no change)

BIT 0 (value 1):
  5 has: 1
  Want:  0

  Check current node:
    children[0]: no ✗
    children[1]: yes (25)

  Decision: Must take children[1] (no choice)
  XOR so far: 11100 = 28 (no change)

RESULT: The Trie path led us to 25!
        5 XOR 25 = 28

Verify:
  5  = 00101
  25 = 11001
  XOR = 11100 = 28 ✓

The Trie helped us find 25 quickly without
checking all other numbers! ⚡

Same Process for ALL Numbers:

For number 3:
  Navigate Trie with bits of 3
  Find best partner → Result: 26

For number 10:
  Navigate Trie with bits of 10
  Find best partner → Result: 19

For number 5:
  Navigate Trie with bits of 5
  Find best partner → Result: 28 ✓

For number 25:
  Navigate Trie with bits of 25
  Find best partner → Result: 28 (same pair!)

For number 2:
  Navigate Trie with bits of 2
  Find best partner → Result: 27

For number 8:
  Navigate Trie with bits of 8
  Find best partner → Result: 17

Global Maximum: 28

Each navigation: O(32) = O(1)
Total: O(n) for all numbers! 🎯

Binary Trie Structure:

Binary Trie Node - Only 2 children!

class TrieNode {
    TrieNode[] children = new TrieNode[2];  // Just 0 and 1!
}

Much simpler than 26 children for String Trie! ✨

Each level represents one bit position:
  Level 0: bit 31 (MSB)
  Level 1: bit 30
  ...
  Level 31: bit 0 (LSB)

Each node branches into:
  children[0]: numbers with 0 at this bit
  children[1]: numbers with 1 at this bit

---

🎯 Solution: Binary Trie + Greedy XOR

Complete Implementation:

class Solution {
    // Binary Trie Node - only 2 children!
    private class TrieNode {
        TrieNode[] children = new TrieNode[2];  // [0] and [1]
    }

    private TrieNode root = new TrieNode();

    public int findMaximumXOR(int[] nums) {
        // Step 1: Build Binary Trie with all numbers
        for (int num : nums) {
            insert(num);
        }

        // Step 2: For each number, find best XOR partner
        int maxXor = 0;
        for (int num : nums) {
            maxXor = Math.max(maxXor, findMaxXorWith(num));
        }

        return maxXor;
    }

    // Insert number into Binary Trie
    private void insert(int num) {
        TrieNode node = root;

        // Process 31 bits (from MSB to LSB)
        for (int i = 31; i >= 0; i--) {
            // Extract i-th bit
            int bit = (num >> i) & 1;

            // Create path if doesn't exist
            if (node.children[bit] == null) {
                node.children[bit] = new TrieNode();
            }

            // Move to next level
            node = node.children[bit];
        }
    }

    // Find maximum XOR for given number
    private int findMaxXorWith(int num) {
        TrieNode node = root;
        int xor = 0;

        // Process 31 bits (from MSB to LSB)
        for (int i = 31; i >= 0; i--) {
            // Extract i-th bit
            int bit = (num >> i) & 1;

            // We want the OPPOSITE bit for maximum XOR!
            int oppositeBit = 1 - bit;  // 0→1, 1→0

            if (node.children[oppositeBit] != null) {
                // Great! Opposite bit exists - use it
                xor |= (1 << i);  // Set this bit in result
                node = node.children[oppositeBit];
            } else {
                // Must use same bit (no choice)
                // This bit contributes 0 to XOR
                node = node.children[bit];
            }
        }

        return xor;
    }
}

---

🔍 Detailed Dry Run - Complete Algorithm

Input: nums = [3, 10, 5, 25, 2, 8]

Binary representations (5 bits for clarity):
  3  = 00011
  10 = 01010
  5  = 00101
  25 = 11001
  2  = 00010
  8  = 01000

PHASE 1: Build Binary Trie (Insert All Numbers)

═══════════════════════════════════════════════════
BUILD TRIE - INSERT ALL NUMBERS
═══════════════════════════════════════════════════

Insert 3 = 00011:
  Path: 0 → 0 → 0 → 1 → 1

Insert 10 = 01010:
  Path: 0 → 1 → 0 → 1 → 0

Insert 5 = 00101:
  Path: 0 → 0 → 1 → 0 → 1

Insert 25 = 11001:
  Path: 1 → 1 → 0 → 0 → 1

Insert 2 = 00010:
  Path: 0 → 0 → 0 → 1 → 0

Insert 8 = 01000:
  Path: 0 → 1 → 0 → 0 → 0

Final Trie Structure (5 bits shown):

        root
       /    \
   [0]        [1]
    |          |
(3,10,5,2,8)  (25)

All numbers inserted! ✓
═══════════════════════════════════════════════════

PHASE 2: Find Maximum XOR (Check Every Number)

═══════════════════════════════════════════════════
PROCESS NUMBER 1: 3 = 00011
═══════════════════════════════════════════════════

Bit 4: 3 has 0, want 1
  → children[1] exists? YES (25)
  → Take it! XOR bit = 1

Bit 3: 3 has 0, want 1
  → On path to 25, want 1
  → children[1] exists? YES
  → Take it! XOR bit = 1

Bit 2: 3 has 0, want 1
  → On path to 25, want 1
  → children[1] exists? NO
  → Must take 0

Bit 1: 3 has 1, want 0
  → children[0] exists? YES
  → Take it! XOR bit = 1

Bit 0: 3 has 1, want 0
  → children[0] exists? NO
  → Must take 1

Result for 3: XOR = 11010 = 26
Best partner for 3 = 25

maxXOR = 26

═══════════════════════════════════════════════════
PROCESS NUMBER 2: 10 = 01010
═══════════════════════════════════════════════════

Bit 4: 10 has 0, want 1
  → children[1] exists? YES (25)
  → Take it! XOR bit = 1

Bit 3: 10 has 1, want 0
  → On path to 25, has 1
  → children[0] exists? NO
  → Must take 1

Bit 2: 10 has 0, want 1
  → children[1] exists? NO
  → Must take 0

Bit 1: 10 has 1, want 0
  → children[0] exists? YES
  → Take it! XOR bit = 1

Bit 0: 10 has 0, want 1
  → children[1] exists? YES
  → Take it! XOR bit = 1

Result for 10: XOR = 10011 = 19
Best partner for 10 = 25

maxXOR = max(26, 19) = 26

═══════════════════════════════════════════════════
PROCESS NUMBER 3: 5 = 00101
═══════════════════════════════════════════════════

Bit 4: 5 has 0, want 1
  → children[1] exists? YES (25)
  → Take it! XOR bit = 1

Bit 3: 5 has 0, want 1
  → children[1] exists? YES
  → Take it! XOR bit = 1

Bit 2: 5 has 1, want 0
  → children[0] exists? YES
  → Take it! XOR bit = 1

Bit 1: 5 has 0, want 1
  → children[1] exists? NO
  → Must take 0

Bit 0: 5 has 1, want 0
  → children[0] exists? NO
  → Must take 1

Result for 5: XOR = 11100 = 28 ✓
Best partner for 5 = 25

maxXOR = max(26, 19, 28) = 28 ← NEW MAXIMUM!

═══════════════════════════════════════════════════
PROCESS NUMBER 4: 25 = 11001
═══════════════════════════════════════════════════

Bit 4: 25 has 1, want 0
  → children[0] exists? YES (3,10,5,2,8)
  → Take it! XOR bit = 1

Following similar logic...

Result for 25: XOR = 11100 = 28
Best partner for 25 = 5 (same pair!)

maxXOR = max(26, 19, 28, 28) = 28

═══════════════════════════════════════════════════
PROCESS NUMBER 5: 2 = 00010
═══════════════════════════════════════════════════

Following similar logic...

Result for 2: XOR = 11011 = 27
Best partner for 2 = 25

maxXOR = max(26, 19, 28, 28, 27) = 28

═══════════════════════════════════════════════════
PROCESS NUMBER 6: 8 = 01000
═══════════════════════════════════════════════════

Following similar logic...

Result for 8: XOR = 10001 = 17
Best partner for 8 = 25

maxXOR = max(26, 19, 28, 28, 27, 17) = 28

═══════════════════════════════════════════════════

FINAL ANSWER: 28

The winning pair: 5 XOR 25 = 28
(Found when processing either 5 or 25)

═══════════════════════════════════════════════════

Key Observations:

1. We processed ALL 6 numbers
   - Each found its best partner using Trie
   - Each took O(32) = O(1) time

2. Multiple numbers can give same max
   - 5 finds partner 25 → XOR = 28
   - 25 finds partner 5 → XOR = 28
   - Same pair, found from both sides!

3. Total time: O(n)
   - Build Trie: O(6) = O(n)
   - Find max: O(6) = O(n)
   - Much better than O(n²) brute force!

4. The Trie helped us avoid checking all pairs
   - Without Trie: 6 * 6 = 36 XOR operations
   - With Trie: 6 * 32 = 192 bit operations
   - But bit operations are much simpler!
   - And for large n, savings are HUGE!

---

📊 Complexity Analysis

Time Complexity:

n = number of elements
L = number of bits (32 for integers)

Build Trie:
  - Insert n numbers
  - Each insert: O(L) = O(32) = O(1)
  - Total: O(n)

Find max XOR:
  - Check n numbers
  - Each check: O(L) = O(32) = O(1)
  - Total: O(n)

Overall: O(n) + O(n) = O(n) ✨

Compare with brute force:
  - Try all pairs: O(n²)

Trie approach is MUCH better! 🏆

Space Complexity:

Worst case:
  - All numbers have completely different bits
  - Each number creates new path
  - Total nodes: O(n * L) = O(32n) = O(n)

Best case:
  - All numbers share prefixes
  - Fewer nodes needed
  - Still O(n) in practice

Space: O(n) 🎯

---

🎯 Pattern Recognition - Binary Trie Applications

Core Pattern: Binary Representation + Greedy Selection

Template for Binary Trie problems:

class TrieNode {
    TrieNode[] children = new TrieNode[2];  // 0 and 1
}

void insert(int num) {
    TrieNode node = root;
    for (int i = 31; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (node.children[bit] == null) {
            node.children[bit] = new TrieNode();
        }
        node = node.children[bit];
    }
}

int findMax(int num) {
    TrieNode node = root;
    int result = 0;
    for (int i = 31; i >= 0; i--) {
        int bit = (num >> i) & 1;
        int want = 1 - bit;  // Opposite for XOR
        if (node.children[want] != null) {
            result |= (1 << i);
            node = node.children[want];
        } else {
            node = node.children[bit];
        }
    }
    return result;
}

Related Problems:

1. Maximum XOR With an Element From Array (1707)

Binary Trie + Sorting
- Add constraint: elements must be <= m
- Build Trie incrementally

2. Count Pairs With XOR in Range (1803)

Binary Trie + Range query
- Count pairs with XOR in [low, high]
- Use Trie for efficient counting

3. Maximum Genetic Difference Query (1938)

Binary Trie + Tree traversal
- DFS on tree
- Maintain Trie of ancestors

When to Use Binary Trie:

✓ XOR optimization problems
✓ Bit manipulation at scale
✓ Need greedy bit selection
✓ Binary representation matters
✓ Maximum/minimum XOR queries

Pattern recognition:
  If problem mentions "maximum XOR" → Think Binary Trie! 🔑

---

🆚 Comparison: String Trie vs Binary Trie

┌──────────────────────────────────────────────────┐
│        STRING TRIE vs BINARY TRIE                │
├──────────────┬────────────────┬──────────────────┤
│ Feature      │ String (161)   │ Binary (163)     │
├──────────────┼────────────────┼──────────────────┤
│ Children     │ 26 (a-z)       │ 2 (0,1)          │
│ Edge Label   │ Character      │ Bit              │
│ Path         │ Word           │ Number           │
│ Levels       │ Word length    │ 32 (int bits)    │
│ isEndOfWord  │ Yes            │ No (all paths)   │
│ Use Case     │ Strings        │ Numbers/XOR      │
│ Insert       │ O(m)           │ O(32) = O(1)     │
│ Search       │ O(m)           │ O(32) = O(1)     │
└──────────────┴────────────────┴──────────────────┘

Same structure, different alphabet! 🎯

---

📝 Quick Revision Notes

🎯 Core Concept

Binary Trie stores numbers as 32-bit paths (MSB to LSB). Each node has 2 children [0,1]. To maximize XOR, greedily choose opposite bit at each level (if exists). Insert: O(32)=O(1), Find: O(32)=O(1), Total: O(n) for n numbers. Much better than O(n²) brute force. XOR maximized when bits are different - greedy strategy works!

⚡ Quick Implementation

class TrieNode {
  TrieNode[] children;
  boolean isEnd;

  public TrieNode() {
    // Just space allocated. All are NULLs.
    // For example, this.children[0] = null, this.children[1] = null and so on till this.children[25] = null
    // Why null? We will initialize with new TrieNode() only when character comes. Why unncessary space before char comes?
    // Check insert method. Only when character comes, we go and initialize that element in the array.
    // For binary numbers, you do need 26 (as its just 0 or 1). Also, isEnd is not required. 
    // But lets use the same for all problems to have it generic.
    this.children = new TrieNode[2];
    this.isEnd = false;
  }  
}

public class Solution {
  public int findMaximumXOR(int[] nums) {
    TrieNode root = new TrieNode();

    // Insert in Trie.
    for(int num : nums) {
      insert(num, root);
    }

    // Find maxXor at each num.
    int maxXor = Integer.MIN_VALUE;
    for(int num : nums) {
      // getMaxXOR finds maxXOR for a particular num out of all numbers of array.
      int numMaxXOR = getMaxXOR(num, root);
      maxXor = Math.max(maxXor, numMaxXOR);
    }

    return maxXor;
  }

    private int getMaxXOR(int num, TrieNode curr) {
    int xor = 0;

    for(int i = 31; i >= 0; i--) {
      int bit = (num >> i) & 1;

      // In order to get a max XOR, number should be opposite. 
      // For 1 in 3, to get max xor for 3, we need to have 0 (1 - 1) in other number.
      int oppositeBit = 1 - bit;

      // Now, check we have this oppositeBit in any of existing TrieNode at this floor (curr)
      if(curr.children[oppositeBit] != null) {
        xor = xor | (1 << i); // GOTCHA: << shifts i many places
        curr = curr.children[oppositeBit];
      } else {
        xor = xor | (0 >> i); // nothing to set. Leave it. You no need to have this line also.
        curr = curr.children[bit];
      }
    }

    return xor;
  }

  private void insert(int num, TrieNode curr) {
    // Concept: A number being inserted to Trie is assumed to be a 32-bit number. Hence, 32 levels (floors)
    // Each floor will have only 2 rooms (0 or 1)
    // Consider 3 as 32-bit number. Start from bit 31, we have to make occupy the floor according to the bit (0 or 1)    
    // 3 => 00000000000000000000000000000011
    // >>31 = 00000000000000000000000000000000 (0) => right shift by 31
    // >>30 = 00000000000000000000000000000000 (0)
    // >>29 = 00000000000000000000000000000000 (0)
    // ...
    // >> 2 = 00000000000000000000000000000000 (0)
    // >> 1 = 00000000000000000000000000000001 (1)
    // >> 0 = 00000000000000000000000000000011 (3)
    // With this for loop, you will get a 32 floor building with each 2 rooms. 
    // Note: At any time, only 1 room gets occupied which depends upon bit. Similar to character of the word.
    for(int i = 31; i >= 0; i--) {
      int bit = (num >> i) & 1; // to have either 0 or 1

      if(curr.children[bit] == null) {
        curr.children[bit] = new TrieNode();
      }

      curr = curr.children[bit];
    }
  }

  public static void main(String[] args) {
        Solution s = new Solution();
    System.out.println(s.findMaximumXOR(new int[] {3,10,5,25,2,8})); // 28
    System.out.println(s.findMaximumXOR(new int[] {14,70,53,83,49,91,36,80,92,51,66,70})); // 127
    }
}

🔑 Key Insights

Greedy Bit Selection:

At each bit position (MSB to LSB):
  Current bit = 0? Want 1!
  Current bit = 1? Want 0!

Why greedy works:
  MSB contributes most to value
  Always try to maximize leftmost bits first

Example:
  1xxxxxxx > 01xxxxxx
  First bit more valuable than all others combined!

Greedy is OPTIMAL! 🔑

Binary Trie vs Array:

ARRAY CHILDREN:
  TrieNode[] children = new TrieNode[2];
  Access: children[bit]  (bit is 0 or 1)

No need for 'ch - 'a'' calculation!
Just use bit value directly! ✨

Bit Extraction:

int bit = (num >> i) & 1;

Explanation:
  num >> i: Right shift by i positions
  & 1: Keep only lowest bit

Examples:
  5 = 0101
  (5 >> 0) & 1 = 0101 & 1 = 1 (bit 0)
  (5 >> 1) & 1 = 0010 & 1 = 0 (bit 1)
  (5 >> 2) & 1 = 0001 & 1 = 1 (bit 2)

Extract any bit position! 🎯

Setting Bits in Result:

xor |= (1 << i);

Explanation:
  (1 << i): Create mask with bit i set
  |=: OR into result (sets bit)

Examples:
  xor = 0000
  xor |= (1 << 2): xor = 0100
  xor |= (1 << 0): xor = 0101

Build result bit by bit! 🔧

🎪 Memory Aid

"2 children, not 26!"
"Bits, not characters!"
"Opposite bit = maximum XOR!"
"Greedy from MSB to LSB!" ✨

⚠️ Don't Forget

• Start from MSB (bit 31, not 0!)
• 2 children only (not 26!)
• Want opposite bit (1-bit for XOR!)
• No isEndOfWord (all paths valid!)
• O(n) total time (not O(n²)!)

---

🎉 Congratulations!

You've mastered Binary Trie - applying Trie to numbers!

What You Learned:

✅ Binary Trie - 2 children instead of 26
✅ Bit representation - Numbers as binary paths
✅ Greedy XOR - Opposite bit selection
✅ Bit manipulation - Extract and set bits
✅ O(n) solution - Better than O(n²) brute force
✅ Pattern transfer - String Trie → Binary Trie

The Beautiful Generalization:

Problem 161: String Trie
  - 26 children (a-z)
  - Characters

Problem 163: Binary Trie
  - 2 children (0-1)
  - Bits

SAME STRUCTURE, DIFFERENT DATA! 🎯

Trie is a GENERAL concept!
  - String Trie: alphabet = 26 letters
  - Binary Trie: alphabet = 2 bits
  - Could be ANY alphabet!

Understanding this = mastery! 💡

Interview Mastery:

Interviewer: "Find maximum XOR of two numbers"

Your response:
  "Classic Binary Trie problem!

   Brute force: Try all pairs - O(n²)

   Optimized: Binary Trie - O(n)

   Approach:
   1. Store all numbers in Binary Trie
      - Each number = 32-bit path
      - 2 children per node [0,1]
      - MSB to LSB order

   2. For each number, find best XOR partner
      - Greedily choose opposite bit
      - Maximize from most significant bit
      - If opposite exists, use it
      - Otherwise, use same bit

   Why greedy works:
   - MSB contributes most to value
   - Always maximize leftmost bits first
   - Greedy = optimal for XOR maximization

   Complexity:
   - Build Trie: O(n * 32) = O(n)
   - Find max: O(n * 32) = O(n)
   - Space: O(n * 32) = O(n)

   Much better than O(n²) brute force!"

Shows complete understanding! 💯

You've now mastered three Trie variations - string, wildcard, and binary! 🏆✨🎯