☕ DSA Java Articles

Topics › Tries › Problems

Maximum Xor with an element from an array

Hard TUF ID 1025 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums of non-negative integers and a list of queries, where queries[i] = [x, m]. The answer to a query is the maximum of x ^ nums[j] over all elements with nums[j] ≤ m. If every element is greater than m, the answer is -1. Return the answers in query order.

Constraints (LeetCode 1707): 1 ≤ n, q ≤ 10^5, and 0 ≤ nums[j], x, m ≤ 10^9.

Example 1

nums    = [0, 1, 2, 3, 4]
queries = [[3, 1], [1, 3], [5, 6]]
answer  = [3, 3, 7]
// [3, 1]: allowed {0, 1}: 3^0 = 3, 3^1 = 2           -> 3
// [1, 3]: allowed {0, 1, 2, 3}: best is 1^2 = 3      -> 3
// [5, 6]: everything allowed: best is 5^2 = 7        -> 7

Example 2

nums    = [5, 2, 4, 6, 6, 3]
queries = [[12, 4], [8, 1], [6, 3]]
answer  = [15, -1, 5]
// [12, 4]: allowed {2, 4, 3}: 12^3 = 15
// [8, 1]:  no element is <= 1                          -> -1
// [6, 3]:  allowed {2, 3}: 6^3 = 5

Approach 1: Brute force

Intuition. Answer each query on its own: scan the array, skip elements above the limit, and keep the best XOR. Since x ^ v ≥ 0 for non-negative values, starting best at -1 gives the “no element allowed” answer for free.

Algorithm.

  1. For each query [x, m]: best = -1.
  2. For each v in nums with v ≤ m: best = max(best, x ^ v).
  3. Store best.
static int[] bruteForce(int[] nums, int[][] queries) {
    int[] ans = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int x = queries[q][0], m = queries[q][1], best = -1;
        for (int v : nums) {
            if (v <= m) best = Math.max(best, v ^ x);  // v ^ x >= 0, so -1 survives only if nothing qualifies
        }
        ans[q] = best;
    }
    return ans;
}

Complexity. Time O(n · q), which is 10^10 at the limits. Space O(1) beyond the output.

Approach 2: Optimal, offline queries with a growing trie

Intuition. Without the limit, each query is “best XOR partner for x”. The binary trie from the maximum XOR problem answers that in 31 steps: walk from bit 30 down and take the child with the opposite bit whenever it exists, because one higher bit is worth more than all lower bits together. The limit m is the obstacle. The trie should contain only the elements ≤ m, but a different m for every query seems to need a different trie.

The way out is to choose the order in which we answer the queries. Sort the queries by m. As m grows, the set of allowed elements only grows, never shrinks. Sort nums as well and keep a pointer: before answering a query, insert every element up to its limit. Each element enters the trie once, and each query then runs the unlimited walk on a trie holding exactly its allowed elements. Answering in a different order than asked is fine as long as each answer goes back to its original index; this is what “offline” means.

Algorithm.

  1. Copy and sort nums. Sort the query indices by m.
  2. For each query index in that order: insert sorted[inserted++] while it is ≤ m. If nothing has been inserted yet, the answer is -1. Otherwise it is maxXorWith(root, x).
  3. Write each answer to its original position.

The trie and its walk are the same as in the two-number problem:

static class Node {
    final Node[] child = new Node[2];
}

static void insert(Node root, int v) {
    Node cur = root;
    for (int b = HIGH_BIT; b >= 0; b--) {
        int bit = (v >> b) & 1;
        if (cur.child[bit] == null) cur.child[bit] = new Node();
        cur = cur.child[bit];
    }
}

static int maxXorWith(Node root, int x) {
    Node cur = root;
    int result = 0;
    for (int b = HIGH_BIT; b >= 0; b--) {
        int want = 1 - ((x >> b) & 1);
        if (cur.child[want] != null) {
            result |= 1 << b;
            cur = cur.child[want];
        } else {
            cur = cur.child[1 - want];
        }
    }
    return result;
}

static int[] optimalOffline(int[] nums, int[][] queries) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    Integer[] order = new Integer[queries.length];
    for (int i = 0; i < order.length; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(queries[a][1], queries[b][1]));   // by limit m
    Node root = new Node();
    int[] ans = new int[queries.length];
    int inserted = 0;                                  // sorted[0 .. inserted - 1] are in the trie
    for (int q : order) {
        int x = queries[q][0], m = queries[q][1];
        while (inserted < sorted.length && sorted[inserted] <= m) insert(root, sorted[inserted++]);
        ans[q] = inserted == 0 ? -1 : maxXorWith(root, x);
    }
    return ans;
}

Dry run on Example 2. Sorted nums = [2, 3, 4, 5, 6, 6], and the queries ordered by m are [8, 1], [6, 3], [12, 4]:

Query (x, m) Inserted now Trie holds Answer
(8, 1) none {} -1
(6, 3) 2, 3 {2, 3} 6 ^ 3 = 5
(12, 4) 4 {2, 3, 4} 12 ^ 3 = 15

Placed back in the original order, the answers are [15, -1, 5].

Complexity. Time O(n log n + q log q) for the sorts, plus O(31 · (n + q)) for all inserts and walks. Space O(31 · n) trie nodes plus O(q) for the index order.

Approach 3: Optimal online, a trie that remembers subtree minimums

Intuition. Sometimes queries must be answered in the order they arrive, for example when they come from a stream. Then we cannot sort them, and the trie must hold every element while still respecting the limit. Store in every node the smallest element in its subtree. A branch contains at least one allowed element exactly when its minimum is ≤ m. The greedy walk becomes: prefer the opposite-bit child, but only if its minimum is ≤ m; otherwise take the other child.

Why the other child is always usable: the walk keeps the invariant cur.min ≤ m. A node’s minimum is the smaller of its two children’s minimums. If the preferred child is missing or has minimum > m, the other child must hold the element that gives cur.min, so it exists and satisfies the limit. The invariant starts at the root, because we answer -1 up front when root.min > m.

Algorithm.

  1. Insert every element, updating min on every node along its path, the root included.
  2. For each query: if the array is empty or root.min > m, answer -1. Otherwise walk from bit 30 down, preferring the opposite-bit child when it exists and its min ≤ m, setting the result bit when that branch is taken.
static class MinNode {
    final MinNode[] child = new MinNode[2];
    int min = Integer.MAX_VALUE;                       // smallest number stored in this subtree
}

static int[] optimalOnline(int[] nums, int[][] queries) {
    MinNode root = new MinNode();
    for (int v : nums) {
        MinNode cur = root;
        cur.min = Math.min(cur.min, v);
        for (int b = HIGH_BIT; b >= 0; b--) {
            int bit = (v >> b) & 1;
            if (cur.child[bit] == null) cur.child[bit] = new MinNode();
            cur = cur.child[bit];
            cur.min = Math.min(cur.min, v);
        }
    }
    int[] ans = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int x = queries[q][0], m = queries[q][1];
        if (nums.length == 0 || root.min > m) {        // every number is above the limit
            ans[q] = -1;
            continue;
        }
        MinNode cur = root;                            // invariant: cur.min <= m
        int result = 0;
        for (int b = HIGH_BIT; b >= 0; b--) {
            int want = 1 - ((x >> b) & 1);
            MinNode preferred = cur.child[want];
            if (preferred != null && preferred.min <= m) {
                result |= 1 << b;
                cur = preferred;
            } else {
                cur = cur.child[1 - want];             // must hold the number that gave cur.min <= m
            }
        }
        ans[q] = result;
    }
    return ans;
}

On Example 1, query [3, 1] with x = 011: bits 30 to 3 are 0 in every element, so the walk follows the 0-branch there. At bit 2, x has a 0 and wants a 1. The 1-branch holds {4}, but its minimum 4 > 1, so the walk rejects it and takes the 0-branch {0, 1, 2, 3} (minimum 0) without setting the bit. At bit 1, x has a 1 and wants a 0. The 0-branch holds {0, 1} with minimum 0 ≤ 1, so the walk takes it and sets the bit. At bit 0, x has a 1 and wants a 0. The 0-branch holds {0}, so the walk takes it and sets the bit. The result is 011 = 3 = 3 ^ 0. An unlimited walk would have taken 4 at bit 2 and returned 3 ^ 4 = 7, which breaks the limit.

Complexity. Time O(31 · (n + q)) with no sorting. Space O(31 · n) nodes, each with one extra int.

Edge cases and pitfalls