Maximum XOR of Two Numbers in an Array

Bit ManipulationTrie

30 min

Problem Statement

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 is less than or equal to i, which is less than or equal to j, which is less than n.

Example

Example 1:

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

Output: 28

Explanation: The maximum result is 5 XOR 25 = 28.

Solution (Trie)

To find the maximum XOR value for each number, we can use a Trie (prefix tree) to store the binary representations of the numbers seen so far. For each number, we traverse the Trie to find a previously inserted number that will maximize the XOR result.

To maximize the XOR, we greedily try to find a path in the Trie that has the opposite bit at each position. If the current bit of our number is 1, we want to find a 0 in the Trie, and vice versa.

Algorithm Steps

Create a Trie data structure.
Insert the binary representation of each number in the input array into the Trie.
For each number in the array, traverse the Trie to find the number that would give the maximum XOR.
Start from the most significant bit. If the current bit is 1, try to go to the 0 child in the Trie. If it's 0, try to go to the 1 child.
If the desired opposite path exists, take it and add a 1 to the current maximum for that number. If not, take the existing path.
Keep track of the overall maximum XOR value found across all numbers.

Input `nums`

31052528

Trie Structure

Current Number: N/A

Current Max XOR: N/A

Overall Max XOR: 0

Initialize an empty Trie and max_xor = 0.

Maximum XOR Solution


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

class Solution:
    def findMaximumXOR(self, nums: list[int]) -> int:
        root = TrieNode()
        L = len(bin(max(nums))) - 2
        
        for num in nums:
            node = root
            for i in range(L - 1, -1, -1):
                bit = (num >> i) & 1
                if bit not in node.children:
                    node.children[bit] = TrieNode()
                node = node.children[bit]
        
        max_xor = 0
        for num in nums:
            node = root
            current_xor = 0
            for i in range(L - 1, -1, -1):
                bit = (num >> i) & 1
                opposite_bit = 1 - bit
                current_xor <<= 1
                if opposite_bit in node.children:
                    current_xor |= 1
                    node = node.children[opposite_bit]
                else:
                    node = node.children[bit]
            max_xor = max(max_xor, current_xor)
            
        return max_xor