Maximum XOR of Two Numbers

▶

Steps

setup

Initialize Trie and Prepare to Insert First Number (3)

Create an empty trie and prepare to insert the first number, 3, processing its bits from the 31st (MSB) to the 0th (LSB).

💡 Initializing the trie is essential to store all numbers bit-by-bit for efficient XOR queries.

Line:

trie = Trie()
num = 3
trie.insert(num)

💡 The trie starts empty and will be built by inserting each number's bits from MSB to LSB.

insert

Insert bit 31 of number 3 into trie

Extract the 31st bit of 3 (which is 0) and insert it into the trie. Since this path does not exist, create a new node for bit 0.

💡 Inserting bits one by one builds the trie structure representing all numbers in binary form.

Line:

bit = (num >> 31) & 1
if bit not in node.children:
    node.children[bit] = TrieNode()

💡 The trie grows dynamically as new bit paths are inserted for each number.

insert

Insert bit 30 of number 3 into trie

Move to the 30th bit of 3 (also 0) and insert it into the trie under the previously created node for bit 0.

💡 Continuing insertion bit-by-bit ensures the trie fully represents the number's binary form.

Line:

bit = (num >> 30) & 1
if bit not in node.children:
    node.children[bit] = TrieNode()

💡 Each bit extends the trie path deeper, representing the number's bits.

insert

Insert bit 1 of number 3 into trie

Insert the 1st bit of 3 (which is 1) into the trie, creating a new branch distinct from previous zeros.

💡 Bits with value 1 create branches distinct from 0 bits, differentiating numbers in the trie.

Line:

bit = (num >> 1) & 1
if bit not in node.children:
    node.children[bit] = TrieNode()

💡 The trie branches at bits where numbers differ, enabling XOR maximization later.

insert

Insert bit 0 of number 3 into trie

Insert the 0th bit of 3 (which is 1), completing the insertion of the number's bits into the trie.

💡 Completing insertion ensures the trie fully represents the number for future XOR queries.

Line:

bit = (num >> 0) & 1
if bit not in node.children:
    node.children[bit] = TrieNode()

💡 The trie now contains the full bit path for number 3.

insert

Insert next number 10 into trie starting at bit 31

Begin inserting the next number, 10, starting from the 31st bit. Check if bit 0 exists in trie and move down existing path if so.

💡 Numbers with common prefixes share trie nodes, saving space and enabling efficient queries.

Line:

num = 10
bit = (num >> 31) & 1
if bit not in node.children:
    node.children[bit] = TrieNode()

💡 Common leading zeros share trie nodes.

insert

Insert bit 3 of number 10 into trie

Insert the 3rd bit of 10 (which is 1). Since this bit path does not exist, create a new node for bit 1.

💡 New bits create new branches in the trie, differentiating numbers.

Line:

bit = (num >> 3) & 1
if bit not in node.children:
    node.children[bit] = TrieNode()

💡 Trie branches represent bit differences between numbers.

traverse

Start traversal to find max XOR for number 5

Begin traversing the trie to find the number that maximizes XOR with 5. At bit 31, bit is 0, toggled bit is 1, but no child 1 exists, so move down bit 0 path.

💡 Choosing opposite bits at each step maximizes XOR bitwise.

Line:

node = trie.root
max_xor = 0
for i in range(31, -1, -1):
    bit = (num >> i) & 1
    toggled_bit = 1 - bit
    if toggled_bit in node.children:
        max_xor |= (1 << i)
        node = node.children[toggled_bit]
    else:
        node = node.children.get(bit)

💡 If opposite bit path exists, XOR bit is set to 1; else follow same bit path.

traverse

Traverse bit 4 for number 5 to maximize XOR

At bit 4, bit of 5 is 0, toggled bit is 1, which exists in trie. Set bit 4 in max_xor and move down that path.

💡 Choosing the opposite bit path sets the XOR bit to 1 at that position, increasing XOR value.

Line:

bit = (num >> 4) & 1
if toggled_bit in node.children:
    max_xor |= (1 << 4)
    node = node.children[toggled_bit]

💡 This step contributes a 1 in the XOR result at bit 4.

traverse

Traverse bit 3 for number 5 to maximize XOR

At bit 3, bit of 5 is 0, toggled bit is 1, which exists in trie. Set bit 3 in max_xor and move down that path.

💡 Continuing to pick opposite bits maximizes XOR bitwise.

Line:

bit = (num >> 3) & 1
if toggled_bit in node.children:
    max_xor |= (1 << 3)
    node = node.children[toggled_bit]

💡 XOR bit 3 is set to 1, increasing max_xor by 8.

traverse

Traverse bit 0 for number 5 to maximize XOR

At bit 0, bit of 5 is 1, toggled bit is 0. Since bit 0 exists in trie children, set bit 0 in max_xor and move down that path.

💡 If opposite bit exists, set XOR bit; else follow same bit path.

Line:

bit = (num >> 0) & 1
if toggled_bit in node.children:
    max_xor |= (1 << 0)
    node = node.children[toggled_bit]
else:
    node = node.children.get(bit)

💡 XOR bit 0 is set to 1, increasing max_xor by 1.

compare

Update max XOR after checking number 5

After traversal, the maximum XOR found for number 5 is 25. Update max_xor from 0 to 25.

💡 Tracking the maximum XOR found so far is essential to find the final answer.

Line:

max_xor = max(max_xor, trie.findMaxXor(num))

💡 The maximum XOR so far is 25 after processing number 5.

traverse

Traverse number 25 to find max XOR

Traverse the trie for number 25. At bit 4, bit is 1, toggled bit is 0, which exists, so set bit 4 in max_xor.

💡 Traversal tries to pick opposite bits to maximize XOR at each bit position.

Line:

bit = (num >> 4) & 1
if toggled_bit in node.children:
    max_xor |= (1 << 4)
    node = node.children[toggled_bit]

💡 Setting bit 4 in max_xor contributes 16 to XOR value.

traverse

Traverse bit 3 for number 25 to maximize XOR

At bit 3, bit is 1, toggled bit is 0, which exists in trie. Set bit 3 in max_xor and move down that path.

💡 Continuing to pick opposite bits maximizes XOR.

Line:

bit = (num >> 3) & 1
if toggled_bit in node.children:
    max_xor |= (1 << 3)
    node = node.children[toggled_bit]

💡 XOR bit 3 set to 1, adding 8 to max_xor.

traverse

Traverse bit 0 for number 25 to maximize XOR

At bit 0, bit is 1, toggled bit is 0, which exists in trie. Set bit 0 in max_xor and move down that path.

💡 Final bits can still contribute to XOR maximization.

Line:

bit = (num >> 0) & 1
if toggled_bit in node.children:
    max_xor |= (1 << 0)
    node = node.children[toggled_bit]

💡 XOR bit 0 set to 1, adding 1 to max_xor.

compare

Update max XOR after checking number 25

The maximum XOR found for number 25 is 25, which matches the current max_xor, so no update is needed.

💡 We keep track of the highest XOR found so far.

Line:

max_xor = max(max_xor, trie.findMaxXor(num))

💡 Current max_xor is still 25 after processing 25.

traverse

Traverse number 5 again to find max XOR

Traverse the trie for number 5 again to check for a better XOR. At bit 4, toggled bit 1 exists, setting bit 4 in max_xor.

💡 Repeated traversals check all numbers for maximum XOR pairs.

Line:

max_xor = max(max_xor, trie.findMaxXor(num))

💡 A new maximum XOR of 28 is found with pair (5, 25).

reconstruct

Final max XOR is 28

After processing all numbers, the maximum XOR found is 28, which is the XOR of 5 and 25.

💡 The algorithm returns the maximum XOR found after all traversals.

Line:

return max_xor

💡 The maximum XOR pair is identified by the highest XOR value found.

class TrieNode:
    def __init__(self):
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):  # STEP: Insert bits from MSB to LSB
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()  # STEP: Create new node if needed
            node = node.children[bit]

    def findMaxXor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):  # STEP: Traverse bits from MSB to LSB
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if toggled_bit in node.children:
                max_xor |= (1 << i)  # STEP: Set bit in max_xor
                node = node.children[toggled_bit]
            else:
                node = node.children.get(bit)
        return max_xor

def findMaximumXOR(nums):
    trie = Trie()  # STEP: Initialize trie
    for num in nums:
        trie.insert(num)  # STEP: Insert each number
    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.findMaxXor(num))  # STEP: Find max XOR for each number
    return max_xor

if __name__ == '__main__':
    nums = [3, 10, 5, 25, 2, 8]
    print(findMaximumXOR(nums))  # Output: 28

📊

Maximum XOR of Two Numbers - Watch the Algorithm Execute, Step by Step

Watching the bitwise trie construction and traversal visually reveals how XOR maximization works at the bit level, which is hard to grasp from code alone.

Check MSB of 3

A

0

1

1

=3

B

💡 Starting insertion of number 3 from MSB to LSB

Insert bit 0 at position 31

A

0

1

1

=3

B

💡 Created new trie node for bit 0 at MSB

Insert bit 0 at position 30

A

0

1

1

=3

B

💡 Extended trie path with bit 0 at position 30

Insert bit 1 at position 1

A

0

1

1

=3

B

💡 Created branch for bit 1 at position 1

Insert bit 1 at position 0

A

0

1

1

=3

B

💡 Completed insertion of number 3

Check MSB of 10

A

0

1

0

1

0

=10

B

💡 Traverse existing trie node for bit 0 at MSB

Insert bit 1 at position 3

A

0

1

0

1

0

=10

B

💡 Created new trie node for bit 1 at bit 3

Check bit 31 of 5 and trie

A

0

1

0

1

=5

B

=000000000000000000000000000000000

────────────────

=

0

0

0

0

0

0

0

0

=0

💡 No opposite bit 1 at MSB, follow bit 0 path

Set bit 4 in max_xor

A

0

1

0

1

=5

B

=000010000000000000000000000000000

────────────────

=

0

0

0

0

0

0

0

0

=16

💡 Opposite bit found, XOR bit set to 1 at position 4

Set bit 3 in max_xor

A

0

1

0

1

=5

B

=000110000000000000000000000000000

────────────────

=

0

0

0

0

0

0

0

0

=24

💡 Opposite bit found, XOR bit set to 1 at position 3

Set bit 0 in max_xor

A

0

1

0

1

=5

B

=000110000000000000000000000000000

────────────────

=

0

0

0

0

0

0

0

1

=25

💡 Opposite bit found, XOR bit set to 1 at position 0

Update max_xor to 25

A

0

1

0

1

=5

B

💡 max_xor updated to 25 after traversal

Set bit 4 in max_xor

A

0

1

1

0

0

1

=25

B

=000000000000000000000000000000000

────────────────

=

0

0

0

0

0

0

0

0

=16

💡 Opposite bit found, XOR bit set to 1 at position 4

Set bit 3 in max_xor

A

0

1

1

0

0

1

=25

B

=000000000000000000000000000000000

────────────────

=

0

0

0

0

0

0

0

0

=24

💡 Opposite bit found, XOR bit set to 1 at position 3

Set bit 0 in max_xor

A

0

1

1

0

0

1

=25

B

=000000000000000000000000000000000

────────────────

=

0

0

0

0

0

0

0

1

=25

💡 Opposite bit found, XOR bit set to 1 at position 0

max_xor remains 25

A

0

1

1

0

0

1

=25

B

💡 max_xor unchanged after traversal

Set bits 4 and 3 in max_xor

A

0

1

0

1

=5

B

=000010000000000000000000000000000

────────────────

=

0

0

0

0

0

0

0

0

=28

💡 New max_xor 28 found by choosing opposite bits

Return max_xor = 28

A

0

1

1

1

0

0

=28

B

────────────

=

0

1

1

1

0

0

=28

💡 Maximum XOR of two numbers in input is 28

Key Takeaways

✓ Building a trie of bits from MSB to LSB allows efficient representation of all numbers for XOR queries.

This insight is hard to see from code alone because the trie structure and bitwise operations are abstract without visualization.

✓ During traversal, choosing the opposite bit path whenever possible maximizes the XOR bitwise.

Visualizing this choice at each bit clarifies why XOR is maximized by picking opposite bits.

✓ The maximum XOR is found by comparing XOR values obtained from traversing the trie for each number.

Seeing the max_xor update step-by-step shows how the algorithm finds the global maximum.

Practice

1. You are given an array of integers and a range [low, high]. You need to count the number of pairs (i, j) with i < j such that the XOR of nums[i] and nums[j] lies within the given range. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a brute force nested loop to check all pairs and count those with XOR in the range.

B. Use dynamic programming to store counts of XOR values for prefixes and combine them.

C. Sort the array and use two pointers to find pairs with XOR in the range.

D. Build a bitwise trie of the numbers and for each number, query how many previously inserted numbers produce XOR less than or equal to a limit, then combine results for the range.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting pairs with XOR in a range efficiently, which brute force (nested loops) is too slow for large inputs.

2. Step 2: Identify the suitable data structure

   A bitwise trie allows efficient counting of numbers with XOR less than a limit by traversing bits from most significant to least significant.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitwise trie approach is known to solve XOR range queries optimally [OK]

Hint: Bitwise trie enables efficient XOR range counting [OK]

Common Mistakes:

• Thinking sorting + two pointers works for XOR ranges
• Assuming DP can handle XOR pairs directly
• Believing brute force is optimal

2. You need to design a data structure that efficiently supports insertion of strings, exact search for strings, and prefix-based search queries. Which of the following data structures guarantees optimal time complexity for these operations regardless of the number of stored strings?

easy

A. Hash Set storing all strings for O(1) average search but no efficient prefix search

B. Trie (Prefix Tree) that stores characters in nodes with links to children nodes

C. Sorting all strings and using binary search for prefix queries

D. Using a balanced binary search tree keyed by entire strings

Solution

1. Step 1: Understand operation requirements

   Insertion, exact search, and prefix search must be efficient. Hash sets provide O(1) average search but cannot efficiently support prefix queries.

2. Step 2: Compare data structures

   Tries store characters in nodes allowing O(m) time for insert/search/startsWith, where m is length of word or prefix. Binary search on sorted strings is O(m log n) and BSTs do not support prefix queries efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie supports prefix queries in O(m) time [OK]

Hint: Tries enable prefix queries in O(m) time [OK]

Common Mistakes:

• Confusing hash sets as supporting prefix queries efficiently

3. You are given a list of words and need to find the shortest prefix for each word that uniquely identifies it among all words. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Build a trie where each node tracks how many words pass through it, then find the prefix where frequency is 1.

B. Sort the words and compare only adjacent words to find the shortest unique prefix.

C. Compare each word's prefixes pairwise with all other words to find uniqueness.

D. Use dynamic programming to store prefix uniqueness states for all words.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding shortest unique prefixes efficiently for all words, which suggests a data structure that can share prefixes.

2. Step 2: Evaluate approaches

   Brute force (A) is too slow (O(n^2 * m)). Sorting + adjacent comparison (C) can miss conflicts with non-adjacent words. DP (D) is not a natural fit here. Trie with frequency counts (B) efficiently tracks prefix usage and finds unique prefixes in O(n*m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie frequency counting matches problem needs [OK]

Hint: Trie frequency counts track prefix uniqueness efficiently [OK]

Common Mistakes:

• Assuming sorting adjacent words is sufficient for uniqueness
• Trying brute force despite inefficiency

4. Suppose you want to extend the Trie to support deletion of words. Which of the following approaches correctly handles deletion without breaking prefix searches for other words?

hard

A. Remove the isEnd flag at the last node of the word and delete nodes bottom-up only if they have no children and isEnd is false

B. Delete all nodes corresponding to the word immediately, regardless of children

C. Set isEnd to false at the last node but never delete any nodes

D. Rebuild the entire trie after each deletion to remove unused nodes

Solution

1. Step 1: Understand deletion impact

   Removing isEnd flag marks word as deleted. Nodes can be deleted only if they are not prefixes of other words.

2. Step 2: Delete nodes bottom-up conditionally

   Delete nodes only if they have no children and isEnd is false to avoid breaking other words.

3. Step 3: Avoid unsafe deletions

   Deleting nodes immediately or rebuilding trie is inefficient or breaks other words.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Conditional bottom-up deletion preserves trie correctness [OK]

Hint: Delete nodes only if no children and isEnd is false [OK]

Common Mistakes:

• Deleting nodes without checking children breaks other words

5. Suppose the problem is modified so that words can be reused multiple times to form longer words (e.g., prefixes can be repeated). Which modification to the trie + BFS approach correctly handles this variant?

hard

A. No change needed; the existing BFS approach already handles reuse of words.

B. Modify BFS to enqueue child nodes even if child.word is None, allowing repeated prefixes.

C. Use DFS with memoization to explore repeated prefixes and avoid cycles.

D. Replace trie with a graph where edges represent possible concatenations and run BFS.

Solution

1. Step 1: Understand reuse of words

   Allowing reuse means prefixes can be repeated multiple times, potentially causing cycles in traversal.

2. Step 2: Why DFS with memoization is needed

   DFS with memoization prevents infinite loops by caching results for nodes, correctly handling repeated prefixes and cycles.

3. Step 3: Why other options fail

   Existing BFS assumes no reuse; enqueuing nodes without word breaks prefix condition; graph BFS without cycle handling risks infinite loops.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DFS + memoization handles repeated prefixes safely [OK]

Hint: Reuse requires cycle-safe DFS with memoization [OK]

Common Mistakes:

• Assuming BFS handles reuse without changes
• Enqueueing invalid nodes breaks prefix rules
• Ignoring cycles in graph representation