Maximum Xor After Operations - Leetcode Solution

The Maximum XOR After Operations problem on LeetCode is a bit challenging and requires a good understanding of bitwise operations and the Trie data structure.

Problem Statement:

Given an array of integers nums and two integers xorVal and threshold, you are asked to perform the following operation:

• each integer of the array nums is XORed (bitwise XOR) with xorVal (every element nums[i] becomes nums[i] ^ xorVal).
• Replace every element nums[i] that is less than or equal to threshold with 0.

Return the maximum result of after performing the above operation on the array nums.

Example:

Input: nums = [2,3,5,6,8,10], threshold = 4, xorVal = 0 Output: 13 Explanation:

• First, convert all the elements to the XOR of the element and the xorVal.
  • For example, nums = [2,3,5,6,8,10] becomes [2^0,3^0,5^0,6^0,8^0,10^0]=[2,3,5,6,8,10]
• Then, replace all the elements less than or equal to the threshold with 0. nums=[0,3,5,6,8,10]
• The maximum XOR value we can get is 13, since 13 = 5^6 = 101^110.

Solution:

The problem asks us to compute the maximum XOR after two operations on the array of integers. The first operation is XORing all the integers with xorVal, and the second operation is replacing all the integers less than or equal to threshold with 0. We can do these operations in any order, which means we can either XOR first and then replace or replace first and then XOR. However, the order will affect the final result.

We can simplify the problem if we focus on computing the maximum XOR of any two elements in the array after doing the two operations. If we can solve this sub-problem, we can easily find the maximum XOR of the entire array.

To compute the maximum XOR of any two elements in the array, we can use the Trie data structure. The idea is to insert all the XORed elements in a Trie and find the maximum XOR of any two elements. The Trie is a tree-like data structure that stores binary strings. In our case, we will use it to store the binary representation of XORed elements.

We can insert each XORed element in the Trie by traversing its binary representation from the most significant bit (MSB) to the least significant bit (LSB). Each node in the Trie has two child nodes. If the current bit of the XORed element is 0, we move to the left child, and if it is 1, we move to the right child. If a child node does not exist at the current bit position, we create a new node.

To find the maximum XOR of any two elements in the array, we can traverse the Trie again in the same way as we did when inserting the elements. For each element, we start from the root of the Trie and follow the opposite path (left or right) as the corresponding bit in the element's binary representation. At each level of the Trie, we choose the child node that gives maximum XOR with the current element's bit. We repeat this process until we reach a leaf node. The maximum XOR of any two elements is the maximum of all the XORs obtained in this process.

To apply the given threshold to the array, we can simply loop through all the elements and replace those that are less than or equal to the threshold with 0.

Here is the Python implementation of the solution:

class TrieNode:
    def __init__(self):
        self.left = None  # represents 0
        self.right = None  # represents 1


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 getMaxXOR(self, num):
        node = self.root
        maxXOR = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit == 0:
                if node.right:
                    maxXOR += (1 << i)
                    node = node.right
                else:
                    node = node.left
            else:
                if node.left:
                    maxXOR += (1 << i)
                    node = node.left
                else:
                    node = node.right
        return maxXOR


class Solution:
    def findMaximumXOR(self, nums: List[int], threshold: int, xorVal: int) -> int:
        trie = Trie()
        for num in nums:
            xorNum = num ^ xorVal
            if xorNum > threshold:
                trie.insert(xorNum)

        maxXOR = 0
        for num in nums:
            xorNum = num ^ xorVal
            if xorNum <= threshold:
                continue
            maxXOR = max(maxXOR, trie.getMaxXOR(xorNum))
        return maxXOR

The Time complexity of the above solution is O(nlog(maxNum)), where n is the length of the array, and maxNum is the maximum possible value of any element in the array (10^9 in this problem). The space complexity is also O(nlog(maxNum)) because we need to store each element's binary representation in the Trie.

1