We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Maximum XOR of Two Numbers in an Array

Difficulty: Medium

Problem Description

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

Key Insights

The XOR operation has properties that can be exploited to find the maximum result efficiently.
The maximum XOR is influenced by the bit positions of the integers involved; higher bits contribute more to the result.
Using a Trie data structure can help in efficiently finding the maximum XOR for each number in the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can utilize a Trie (prefix tree) to store the binary representations of the numbers. The algorithm works as follows:

Insert each number into the Trie: We insert the numbers bit by bit from the highest bit (31st for 32-bit integers) to the lowest (0th).
Calculate the maximum XOR for each number: For each number, we traverse the Trie to find the number that will maximize the XOR value by choosing the opposite bit whenever possible.
Keep track of the maximum XOR found during these calculations.

This method is efficient and works well within the given constraints.

Code Solutions

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):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
    
    def find_max_xor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            # Try to take the opposite bit to maximize XOR
            toggle_bit = 1 - bit
            if toggle_bit in node.children:
                max_xor |= (1 << i)
                node = node.children[toggle_bit]
            else:
                node = node.children[bit]
        return max_xor

def findMaximumXOR(nums):
    trie = Trie()
    for num in nums:
        trie.insert(num)
    
    max_xor_result = 0
    for num in nums:
        max_xor_result = max(max_xor_result, trie.find_max_xor(num))
    
    return max_xor_result

← Back to All Questions