Maximum XOR With an Element From Array

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [x<sub>i</sub>, m<sub>i</sub>]. The answer to the i<sup>th</sup> query is the maximum bitwise XOR value of x<sub>i</sub> and any element of nums that does not exceed m<sub>i</sub>. In other words, the answer is max(nums[j] XOR x<sub>i</sub>) for all j such that nums[j] <= m<sub>i</sub>. If all elements in nums are larger than m<sub>i</sub>, then the answer is -1. Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i<sup>th</sup> query.

Example 1:

Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

Example 2:

Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]

class Solution:
    def maximizeXor(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        nums.sort() # sort nums for binary search later
        result = []
        for x, m in queries:
            max_xor = -1  # default answer if no element satisfies the condition
            for num in nums:
                if num <= m:
                    max_xor = max(max_xor, num ^ x)
                else:
                    break # optimization: since nums is sorted, no need to check the remaining elements
            result.append(max_xor)
        return result


# Example usage:
nums = [0, 1, 2, 3, 4]
queries = [[3, 1], [1, 3], [5, 6]]
solution = Solution()
print(solution.maximizeXor(nums, queries))  # Output: [3, 3, 7]

nums = [5, 2, 4, 6, 6, 3]
queries = [[12, 4], [8, 1], [6, 3]]
print(solution.maximizeXor(nums, queries))  # Output: [15, -1, 5]

Brute Force Solution Explanation:

The brute force solution iterates through each query [x, m] and, for each query, it iterates through the nums array. For each number in nums, it checks if the number is less than or equal to m. If it is, it calculates the XOR of the number and x and updates the max_xor if the calculated XOR is greater than the current max_xor. If the number is greater than m, it breaks out of the inner loop to avoid unnecessary comparisons since nums is sorted. If no number in nums satisfies the condition num <= m, the max_xor remains -1.

Optimal Solution (Using Trie):

class TrieNode:
    def __init__(self):
        self.children = [None] * 2


class Solution:
    def insert(self, root, num):
        curr = root
        for i in range(31, -1, -1):  # Iterate from MSB to LSB
            bit = (num >> i) & 1
            if not curr.children[bit]:
                curr.children[bit] = TrieNode()
            curr = curr.children[bit]

    def find_max_xor(self, root, num, max_limit):
        curr = root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if curr.children[1 - bit] and (max_limit >> i) & 1:
                max_xor |= (1 << i)
                curr = curr.children[1 - bit]
            elif curr.children[bit] and (max_limit >> i) & 1:
                curr = curr.children[bit]
            else:
                return -1  # No suitable number found
        return max_xor

    def maximizeXor(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        root = TrieNode()
        for num in nums:
            self.insert(root, num)
        result = []
        for x, m in queries:
            max_xor = self.find_max_xor(root, x, m)
            result.append(max_xor)
        return result

# Example usage:
nums = [0, 1, 2, 3, 4]
queries = [[3, 1], [1, 3], [5, 6]]
solution = Solution()
print(solution.maximizeXor(nums, queries))  # Output: [3, 3, 7]

nums = [5, 2, 4, 6, 6, 3]
queries = [[12, 4], [8, 1], [6, 3]]
print(solution.maximizeXor(nums, queries))  # Output: [15, -1, 5]

Optimal Solution Explanation:

1. Trie Data Structure: We use a Trie (prefix tree) to store the binary representation of each number in nums. Each node in the Trie has two children, representing the bits 0 and 1.
2. Insertion: For each number in nums, we insert its binary representation into the Trie. This allows us to efficiently search for numbers with specific bit patterns.
3. Querying: For each query [x, m], we traverse the Trie to find a number that maximizes the XOR value with x and is less than or equal to m.
4. Bitwise Comparison: During the Trie traversal, we compare the bits of x and m to determine which branch to follow. If we find a bit in m that is 0, we can only follow the branch that corresponds to the same bit in the current Trie node. If the bit in m is 1, we can follow the branch that maximizes the XOR value with x, as long as it satisfies the condition num <= m.
5. Return Value: If a suitable number is found in the Trie, we return the maximum XOR value. Otherwise, we return -1.

Big(O) Time Complexity Analysis:

• Brute Force Solution:
  • The time complexity is O(n * q), where n is the length of nums and q is the number of queries. For each query, we iterate through (potentially) all elements of nums. Sorting nums takes O(n log n), but it is dominated by the nested loops.
• Optimal Solution (Trie):
  • Building the Trie takes O(n * 32), where n is the number of elements in nums. The 32 comes from the number of bits in an integer. Therefore, building the Trie is O(n).
  • For each query, searching the Trie takes O(32), which is O(1).
  • Overall, the time complexity of the Trie solution is O(n + q), where n is the length of nums and q is the number of queries.

Big(O) Space Complexity Analysis:

• Brute Force Solution:
  • The space complexity is O(1). We are not using any extra data structures that scale with the input size.
• Optimal Solution (Trie):
  • The space complexity is O(n * 2^b), where n is the number of elements in nums and b is the number of bits in each number. In our case since numbers are up to 10^9, b is roughly 32. Each number can have up to b nodes in the Trie. Each node has 2 children.
  • Therefore, the space complexity of the Trie solution is O(n).

Edge Cases:

1. Empty nums array: If the nums array is empty, there are no elements to XOR with. Therefore, the answer to each query should be -1.
2. Empty queries array: If the queries array is empty, there are no queries to process. Therefore, the function should return an empty array.
3. All elements in nums are greater than m: If all elements in nums are greater than m, the answer to the query should be -1.
4. Large values of x and m: The algorithm should work correctly for large values of x and m (up to 10^9). The Trie data structure should be able to handle numbers with up to 32 bits.