Problem Statement:

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

Example:

Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.

Solution:

Approach: Trie Tree

In this approach, we create a Trie tree and traverse through the tree to find the maximum XOR of any pair of numbers in the given array.

We initialize the Trie with the highest bit first, i.e., 2^31 and move on to compute the maximum XOR of the bits at every position of the two numbers.

We traverse the Trie tree for each of the numbers in the array. If a bit of the current number is 0, we follow the left branch of the Trie Tree. If it's a 1-bit, we follow the right branch. We construct the Trie such that the paths from the root to the leaf form all the possible binary numbers that could be formed using the given array elements.

To find the maximum XOR value, we compare the bits of each number at every level of the Trie tree. We always choose the branch that will give a 1 in the maximum XOR value. We do this because we want to maximize the value of the XOR.

The time complexity of this approach is O(nlog(max_num)) where max_num is the maximum number in the array.

Here's the implementation of the solution:

class TrieNode:

def __init__(self):
    self.left = None
    self.right = None

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 == 0:
            if not node.left:
                node.left = TrieNode()
            node = node.left

        else:
            if not node.right:
                node.right = TrieNode()
            node = node.right

def findMaxXOR(self, nums):
    maxXOR = 0

    for num in nums:
        node = self.root
        currXOR = 0

        for i in range(31, -1, -1):
            bit = (num >> i) & 1

            if bit == 0:
                if node.right:
                    currXOR += 2 ** i
                    node = node.right
                else:
                    node = node.left

            else:
                if node.left:
                    currXOR += 2 ** i
                    node = node.left
                else:
                    node = node.right

        maxXOR = max(maxXOR, currXOR)

    return maxXOR

def findMaximumXOR(nums) -> int: trie = Trie()

for num in nums:
    trie.insert(num)

return trie.findMaxXOR(nums)

testing the code

print(findMaximumXOR([3,10,5,25,2,8]))

Output:

28

Explanation:

In the given example, we construct the Trie and traverse through it for every number in the given array.

The Trie with the given numbers will look like this:

                    1                               #31 bit
              /           \
            0               1                     #30 bit
          /   \           /   \
         1     0         0     1                  #29 bit
        / \   / \       / \   / \
       1   0 1   1     1   0 0   0                #28 bit
      / \ / \ / \     / \ / \ / \
     1  0 1  1 0  0   1  1 1  0 0  0              #27 bit
     ... ... ...     ... ... ... ...

For each number in the given array, we traverse through the Trie and update the maximum XOR value. At each level, we choose the path that gives the maximum XOR value, because we want to maximize the value of XOR.

For the given array [3,10,5,25,2,8], we can get the maximum XOR value of 28, which is obtained by XOR of 5 and 25.

1