Maximum Xor With An Element From Array - Leetcode Solution

Problem Statement:

Given an array nums[] of n integers and an integer x, find the maximum value of nums[i] XOR x where 0 ≤ i < n.

Solution:

The XOR operation is a bit manipulation operation that returns 1 in each bit position where the corresponding bits of one but not both operands are 1s. Given an array of integers and an integer x, we can find the maximum value of nums[i] XOR x by iterating over the array and XORing the current element with the target integer x. However, this approach has a time complexity of O(n^2), which is not efficient for large input sizes.

We can optimize this approach by using a trie data structure to store the binary representation of each integer in the array. A trie is a tree-like data structure in which each node contains bits of a binary number and branches to represent the possible values of the next bit.

We iterate over the elements of the array and insert their binary representation into the trie using each bit as a branch of the trie. We then iterate over the binary representation of the target integer x and follow the branches of the trie that correspond to each bit, choosing the opposite branch if the current bit is a 0 and the same branch if the current bit is a 1.

After reaching the leaf node in the trie corresponding to the binary representation of x, we can find the best matching integer in the array by finding the path in the trie that has the maximum XOR value with the given integer x. To do this, we iterate over each bit of the binary representation of x, starting from the most significant bit. If the current bit is a 0, we follow the path with the opposite branch if it exists, otherwise we follow the same branch. If the current bit is a 1, we follow the path with the same branch if it exists, otherwise we follow the opposite branch.

The maximum XOR value is then the XOR of the integer represented by the final node in the trie with the target integer x.

Algorithm:

1. Create a trie data structure to store the binary representation of each integer in the array.
2. Iterate over the elements of the array and insert their binary representation into the trie using each bit as a branch of the trie.
3. Iterate over the binary representation of the target integer x and follow the branches of the trie that correspond to each bit, choosing the opposite branch if the current bit is a 0 and the same branch if the current bit is a 1.
4. After reaching the leaf node in the trie corresponding to the binary representation of x, iterate over each bit of the binary representation of x, starting from the most significant bit.
5. If the current bit is a 0, follow the path with the opposite branch if it exists, otherwise follow the same branch.
6. If the current bit is a 1, follow the path with the same branch if it exists, otherwise follow the opposite branch.
7. The maximum XOR value is then the XOR of the integer represented by the final node in the trie with the target integer x.

Code:

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

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]
        node.val = num

    def findMaxXOR(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if 1 - bit in node.children:
                node = node.children[1 - bit]
            else:
                node = node.children[bit]
        return num ^ node.val

class Solution:
    def findMaximumXOR(self, nums: List[int], x: int) -> int:
        trie = Trie()
        for num in nums:
            trie.insert(num)
        return trie.findMaxXOR(x)

Time Complexity: O(n log max_num), where n is the length of the input array nums and max_num is the maximum value of any element in nums.

The time complexity of inserting each element into the trie is O(log max_num) and the time complexity of finding the maximum XOR value is also O(log max_num). Since we iterate over each element in the input array once, the overall time complexity is O(n log max_num).

1