algoadvance

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

Clarifying Questions

  1. Constraints:
    • What are the constraints on the size of the array (n)?
      • The array size can be between (1) and (2 \times 10^5).
    • What is the range of values for each element in the array?
      • Each element in the array can be between (0) and (10^9).
    • Can the array contain duplicate elements?
      • Yes, the array can contain duplicate elements.
  2. Input/Output:
    • Will the input always be valid?
      • Yes, the input will always be valid as per the problem constraints.

Strategy

To solve this problem, we need to find two numbers in the array that yield the maximum XOR value when XOR’d together. A brute force approach would be to try every pair of numbers in the array, but this would be too slow for large arrays since it has a time complexity of (O(n^2)).

A more efficient approach involves using a Trie (prefix tree) to store the binary representations of the numbers as we iterate through the array. By using the Trie, we can maximize the XOR value at each bit position:

  1. Insert each number in the Trie.
  2. Query the Trie to find the maximum XOR for each number in the array.
  3. Use properties of XOR and the binary Trie to efficiently find the maximum XOR in (O(n \cdot \log K)) time, where (K) is the maximum bit length of the numbers (which is 30 for numbers up to (10^9)).

Code

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

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

    def insert(self, num):
        node = self.root
        for i in range(self.max_bit_length, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
        node.value = num
    
    def find_max_xor(self, num):
        node = self.root
        max_xor = 0
        for i in range(self.max_bit_length, -1, -1):
            bit = (num >> i) & 1
            toggle_bit = 1 - bit
            if toggle_bit in node.children:
                max_xor = (max_xor << 1) | 1
                node = node.children[toggle_bit]
            else:
                max_xor = (max_xor << 1)
                node = node.children[bit]
        return max_xor

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

# Example usage
nums = [3, 10, 5, 25, 2, 8]
print(findMaximumXOR(nums)) # Output: 28

Time Complexity

This approach is efficient and suitable given the constraints, ensuring that even large arrays are processed within optimal time.

Feel free to ask any further questions or for additional explanations!

Try our interview co-pilot at AlgoAdvance.com