Maximum Xor For Each Query - Leetcode Solution

Problem Description:

You are given an array nums consisting of non-negative integers. You are also given a list of queries queries where each query consists of two integers xi and mi. For each query, find a number in nums such that the bitwise XOR of that number and xi is maximum possible and less than or equal to mi. Return an array ans where ans[i] is the answer to the ith query.

Solution:

Approach:

We can solve this problem using the Trie data structure. We will insert all the numbers from the given array into a Trie. Then for each query we will traverse the Trie according to the bits of the query number xi. While traversing, if there is a bit of xi is 0, then we will try to take the path with 1, and if the bit is 1, then we will try to take the path with 0. At each level of the trie, we will keep track of the maximum XOR encountered so far. If the maximum XOR encountered so far is greater than the given mi, then we will discard that path and move on to the next path. In this way, we will find the maximum XOR number for the given query.

Algorithm:

1. Create an empty trie.
2. Insert all numbers from the given array into the trie.
3. For each query: a. Initialize the max_xor variable to 0. b. Traverse the trie according to the bits of the query number xi. c. At each level, compute the maximum XOR encountered so far by taking the path with the highest bit different from the corresponding bit of xi. d. If the maximum XOR encountered so far is greater than the given mi, then discard that path and move on to the next path. e. Continue until the end of the query number xi is reached. f. Return the maximum XOR encountered so far.

Code:

class TrieNode:
    def __init__(self):
        self.children = {}
        
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]
    
    def find_max_xor(self, xi, mi):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit_xi = (xi >> i) & 1
            bit_mi = (mi >> i) & 1
            if bit_xi == 0:
                if 1 in node.children and ((max_xor | (1 << i)) <= mi):
                    max_xor |= (1 << i)
                    node = node.children[1]
                else:
                    node = node.children[0]
            else:
                if 0 in node.children and ((max_xor | (0 << i)) <= mi):
                    max_xor |= (0 << i)
                    node = node.children[0]
                else:
                    node = node.children[1]
        return max_xor

class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        t = Trie()
        for num in nums:
            t.insert(num)
        ans = []
        for xi, mi in queries:
            ans.append(t.find_max_xor(xi, mi))
        return ans

Time Complexity:

Inserting all the numbers from the given array into trie takes O(n * log(max_num)). In each query, we are traversing at most 31 levels of the trie. At each level, we are performing constant time operations. Therefore, the time complexity of each query is O(log(max_num)). Hence the overall time complexity of the solution is O((n + q) * log(max_num)).

Space Complexity:

The space complexity of the Trie data structure is O(n * log(max_num)).

1