Problem statement

https://leetcode.com/problems/maximum-xor-with-an-element-from-array/

Solution 1

It is similar to problem 0421, where the idea is to build trie given number. Also in this problem we are given our queries in advance, that is so-called offline queries, so we can exploit this and keep in our trie only relevant elements. The idea is to sort queries by m and then add only number which are less or equal to m.

Complexity

Time complexity is O(n log n + k log k + k log M), where n is length of nums, k is length of queries and M is limit for numbers in nums. Space complexity is O(n * log M).

Code

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, num):
        d = self.root
        for i in range(30, -1, -1):
            bit = (num >> i) & 1
            d = d.setdefault(bit, dict())

    def find(self, num):
        if not self.root: return -1
        node, res = self.root, 0
        for i in range(30, -1, -1):
            bit = (num >> i) & 1
            desired = 1-bit if 1-bit in node else bit
            res += (desired ^ bit) << i
            node = node[desired]
        return res

class Solution:
    def maximizeXor(self, nums, Q):
        nums.sort()
        Q = sorted((m, x, i) for i, (x, m) in enumerate(Q))
        trie, n, k = Trie(), len(nums), len(Q)
        ans, ind = [-1] * k, 0
        
        for m, x, i in Q:
            while ind < n and nums[ind] <= m:
                trie.insert(nums[ind])
                ind += 1
            ans[i] = trie.find(x)
        return ans

Solution 2

There is also version where queries are online. The idea is to traverse trie and if:

  1. We have only one children, we need to go in this direction.
  2. If we have 1-bit children, we need to go to this direction, and if we have result -1, it means that this subtree is too big for us, so we need to abandon it and go to the other one.

Complexity

One query can spend potentially upto O(log^2 M) time, because to make sure that branch is bad, we need to go upto leaf. However in practice it works almost the same as previous approach, because I think in average it is still O(log M). So, total time complexity is O(n log n + k*log^2M). Space complexity is O(n * log M).

Code

class Trie:
    def __init__(self):
        self.root = {}
        
    def insert(self, num):
        d = self.root
        for i in range(30, -1, -1):
            bit = (num >> i) & 1
            d = d.setdefault(bit, dict())
        
    def dfs(self, node, x, L, i, res):
        if res > L: return -1
        if i < 0: return res
        bit = (x >> i) & 1
        
        if len(node) == 1:
            c = 0 if 0 in node else 1
            return self.dfs(node[c], x, L, i-1, res+(c<<i))
        
        res2 = self.dfs(node[1-bit], x, L, i-1, res+((1-bit)<<i))
        if res2 < 0: res2 = self.dfs(node[bit], x, L, i-1, res+(bit<<i))
        return res2
    
class Solution:
    def maximizeXor(self, nums, Q):
        trie, res = Trie(), []
        for i in nums: trie.insert(i)

        for x, m in Q:
            ans = trie.dfs(trie.root, x, m, 30, 0)
            res += [ans^x] if ans >= 0 else [-1]
        return res

Solution 3

We can modify our trie a bit and for each node keep minimum value of subtree we can have. If it is more than limit, we can do erly stopping. So, now complexity of query is O(log M), however in practice it works even slower, but from code it is easy to show complexity.

Complexity

Total time complexity is O(n log n + k*log M). Space complexity is O(n * log M).

Code

class Trie:
    def __init__(self):
        self.root = {-1: float("inf")}
        
    def insert(self, num):
        d = self.root
        for i in range(30, -1, -1):
            bit = (num >> i) & 1
            d = d.setdefault(bit, dict())
            d[-1] = min(num, d.get(-1, float("inf")))
        
    def dfs(self, node, x, L, i, res):
        if res > L: return -1
        if i < 0: return res
        bit = (x >> i) & 1
        
        best = -1
        if 1-bit in node and (node[1-bit][-1] <= L or bit not in node): 
            best = 1 - bit
        elif bit in node and (node[bit][-1] <= L or 1-bit not in node):
            best = bit
        
        if best == -1: return -1
        return self.dfs(node[best], x, L, i-1, res+(best<<i))
    
class Solution:
    def maximizeXor(self, nums, Q):
        trie, res = Trie(), []
        for i in nums: trie.insert(i)

        for x, m in Q:
            ans = trie.dfs(trie.root, x, m, 30, 0)
            res += [ans^x] if ans >= 0 else [-1]
        return res