Solution 1: Brute Force

Intuition:

We can use a brute force method where we compute the XOR of each pair of elements and find the maximum value.

Solution:

from typing import List

def max_xor_pair(nums: List[int]) -> int:
    max_xor = 0
    n = len(nums)
    # Iterate through each pair of elements
    for i in range(n):
        for j in range(i + 1, n):
            # Compute the XOR of the pair
            xor_value = nums[i] ^ nums[j]
            # Update the maximum XOR value if necessary
            max_xor = max(max_xor, xor_value)
    return max_xor

# Test cases
nums1 = [3, 10, 5, 25, 2, 8]
result1 = max_xor_pair(nums1)
print(result1)  # Output should be 28

nums2 = [0, 1, 2, 3, 4, 5]
result2 = max_xor_pair(nums2)
print(result2)  # Output should be 7

Time Complexity:

In the brute force approach, we compute the XOR of each pair of elements, resulting in O(n2) comparisons, where n is the number of elements in the array.

Space Complexity:

The space complexity of the brute force approach is O(1) since we are not using any additional data structures that grow with the size of the input array.

Solution 2: Using Trie

Intuition:

To find the maximum XOR value between any two elements in the array, we can use a bitwise trie data structure. The trie will represent the binary representation of the array elements, with each level of the trie corresponding to a bit position (from the most significant bit to the least significant bit). We traverse the trie from the most significant bit to the least significant bit, choosing the path that maximizes the XOR value. By doing so, we can efficiently find the maximum XOR value for each pair of elements in the array.

Solution:

from typing import List

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

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

    def insert(self, num):
        node = self.root
        # Traverse the trie based on the binary representation of the number
        for i in range(31, -1, -1):  # Iterate from the most significant bit to the least significant bit
            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
        xor_num = 0
        # Traverse the trie to maximize the XOR value
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            # Choose the opposite bit if available to maximize the XOR value
            if 1 - bit in node.children:
                xor_num |= (1 << i)  # Set the bit in the result
                node = node.children[1 - bit]
            else:
                node = node.children[bit]
        return xor_num

def max_xor_pair(nums: List[int]) -> int:
    trie = Trie()
    max_xor = 0
    # Insert each number into the trie and find the maximum XOR value
    for num in nums:
        trie.insert(num)
        max_xor = max(max_xor, trie.find_max_xor(num))
    return max_xor

# Test cases
nums1 = [3, 10, 5, 25, 2, 8]
result1 = max_xor_pair(nums1)
print(result1)  # Output should be 28

nums2 = [0, 1, 2, 3, 4, 5]
result2 = max_xor_pair(nums2)
print(result2)  # Output should be 7

Time Complexity:

  • Building the trie: Inserting each number into the trie takes O(32 * n) time, where n is the number of elements in the array. This is because we iterate through each bit (31 to 0) for each number.
  • Finding maximum XOR: For each number, traversing the trie to find the maximum XOR value takes O(32 * n) time in total, as we iterate through each bit again.
  • Therefore, the overall time complexity is O(32 * n), which simplifies to O(n), where n is the number of elements in the array.

Space Complexity:

  • The space complexity of the trie data structure is O(m), where m is the total number of bits used to represent the numbers in the array.
  • Since each number is represented using 32 bits (assuming 32-bit integers), the space complexity is O(n * 32), which simplifies to O(n), where n is the number of elements in the array.