#1707
Maximum XOR With an Element From Array
Hard Offline queries + binary trie
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
For each query [x, m], return the maximum x XOR v over array values v ≤ m, or -1 if no value is ≤ m.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for each query (x, m), the max x XOR v with v ≤ m.
Why this works: sort the queries by m and insert numbers into the trie only while they're ≤ m; then query as usual.
Example: nums [0,1,2,3,4], query (3, 1)
insert 0, 13 ^ 0 = 3, 3 ^ 1 = 2 → 3
✦Hints open one at a time
Answer queries offline: sort them by m.
Sort the array too, and insert values into a binary trie only while they are ≤ the current m.
↗Approach
Sort nums and the queries by m (keeping original indexes). Use a pointer to add nums ≤ m into the trie, then query the best XOR for x as in "Maximum XOR of Two Numbers". If the trie is empty, the answer is −1.
</>Solution (Java)
import java.util.*;
class Solution {
private static class Node {
Node[] child = new Node[2];
}
public int[] maximizeXor(int[] nums, int[][] queries) {
Arrays.sort(nums);
int q = queries.length;
Integer[] order = new Integer[q];
for (int i = 0; i < q; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(queries[a][1], queries[b][1])); // by m
Node root = new Node();
int[] ans = new int[q];
int p = 0;
for (int qi : order) {
int x = queries[qi][0], m = queries[qi][1];
while (p < nums.length && nums[p] <= m) insert(root, nums[p++]);
ans[qi] = (p == 0) ? -1 : best(root, x);
}
return ans;
}
private void insert(Node root, int v) {
Node cur = root;
for (int b = 29; b >= 0; b--) {
int bit = (v >> b) & 1;
if (cur.child[bit] == null) cur.child[bit] = new Node();
cur = cur.child[bit];
}
}
private int best(Node root, int x) {
Node cur = root;
int xor = 0;
for (int b = 29; b >= 0; b--) {
int bit = (x >> b) & 1;
if (cur.child[1 - bit] != null) {
xor |= 1 << b;
cur = cur.child[1 - bit];
} else {
cur = cur.child[bit];
}
}
return xor;
}
}!Common mistake
Answering queries in input order — you'd have to rebuild the trie for each m.
Complexity
- Time: O((n + q) · 30 + n log n + q log q).
- Space: O(n · 30).
Topic: Trie
🎬 Episode 97: video coming soon