Maximum XOR With an Element From Array

Problem

LeetCodeOpen original problem

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [xi, mi].

The answer to the ith query is the maximum bitwise XOR value of xi and any element of nums that does not exceed mi. In other words, the answer is max(nums[j] XOR xi) for all j such that nums[j] <= mi. If all elements in nums are larger than mi, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the ith query.

Solution approach

Intuition

Without the limit m, each query is the classic “maximum XOR with a trie” problem: walk from the highest bit down and prefer the opposite bit at every level. The limit means only numbers <= m may be in the trie. Answer the queries offline, sorted by m: as m grows, insert the numbers that have just become allowed, so each number is inserted only once.

Checking every number for every query would cost $O(n \cdot q)$; sorting both lists avoids that.

Algorithm

1. Append each query’s original index and swap its two values, so each query becomes [m, x, idx]. Sort queries by m, and sort nums.
2. For each query j, insert every nums[i] <= queries[j][0] into the trie with insert, which creates a path over bits 30 to 0.
3. If no number has been inserted (i == 0), the answer is -1. Otherwise query(queries[j][1]) walks the trie, taking the child v[bit == 0] (the opposite bit) when it exists and adding 1 << i to the result.
4. Store the answer at ans[queries[j][2]] so the results come back in the original order.

Complexity

• Time: $O(n \log n + q \log q + 31(n + q))$ — two sorts, then one 31-step trie walk per insertion and per query.
• Space: $O(31 \cdot n + q)$ — the trie nodes plus the answer array.

Edge cases

• All numbers larger than m: nothing has been inserted yet, so the answer is -1.

Code

C++

struct Node {
    vector<Node*> v;
    int val;
    Node(int _val) {
        v = {NULL, NULL};
        val = _val;
    }
};

class Solution {
   public:
    Node* root;

    void insert(int n) {
        Node* temp = root;
        int i = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (n & (1 << i));
            if (temp->v[bit > 0] == NULL) {
                Node* newNode = new Node(bit > 0);
                temp->v[bit > 0] = newNode;
            }
            temp = temp->v[bit ? 1 : 0];
        }
    }

    int query(int n) {
        Node* temp = root;
        int ans = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = n & (1ll << i);
            if (temp->v[bit == 0] != NULL) {
                ans += (1ll << i);
                temp = temp->v[bit == 0];
            } else
                temp = temp->v[bit != 0];
        }
        return ans;
    }

    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        for (int i = 0; i < queries.size(); i++) {
            queries[i].push_back(i);
            swap(queries[i][0], queries[i][1]);
        }
        sort(queries.begin(), queries.end());
        sort(nums.begin(), nums.end());
        root = new Node(0);
        int i = 0, j = 0;
        vector<int> ans(queries.size());
        while (j < queries.size()) {
            while (i < nums.size() && nums[i] <= queries[j][0]) {
                insert(nums[i]);
                i++;
            }

            if (i == 0) {
                ans[queries[j][2]] = -1;
            } else {
                ans[queries[j][2]] = query(queries[j][1]);
            }
            j++;
        }
        return ans;
    }
};

Give it a try first

Attempt the problem on LeetCode — the code will still be here.

Show solutionAlways show solutions

Hide solution