Problem statement

https://binarysearch.com/problems/Maximum-XOR-Queries/

Solution

Equal to Leetcode 1707 Maximum XOR With an Element From Array

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^num

class Solution:
    def solve(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