Maximum XOR With an Element From Array — Problem & Solution
Maximum XOR With an Element From Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum XOR With an Element From Array is a hard coding problem on arrays, sorting and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Bit Manipulation, Trie
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of non-negative integers and an array queries where queries[i] = [xi, mi].
The answer to query i is the largest value of xi XOR nums[j] over all indices j with nums[j] <= mi. If every element of nums is larger than mi, the answer is -1.
Return an array answer with answer[i] the answer to the i-th query.
Example 1
Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation: Query 0 may use 0 and 1: `3 XOR 0 = 3`. Query 1 may use 0..3: `1 XOR 2 = 3`. Query 2 may use everything: `5 XOR 2 = 7`.
Example 2
Input: nums = [6,9,12], queries = [[8,5],[4,10],[0,20]]
Output: [-1,13,12]
Explanation: No element is at most 5. With limit 10, `4 XOR 9 = 13` beats `4 XOR 6 = 2`.
Constraints
1 <= nums.length, queries.length <= 10^5queries[i].length == 20 <= nums[j], xi, mi <= 10^9
Hints for Maximum XOR With an Element From Array
Hint 1
Without the limit this is the classic maximum-XOR query: a binary trie of the numbers, walked greedily from the top bit.
Hint 2
The limit only removes numbers. Can you answer the queries in an order where the allowed set only grows?
Hint 3
Sort
numsand sort the queries bymi; before each query insert every number<= miinto the trie, then walk it preferring the opposite bit ofxi.
How to solve Maximum XOR With an Element From Array
Answer the queries offline in increasing order of mi, so the set of allowed numbers only grows and a single binary trie can hold exactly them.
Approach
- Sort
nums, and sort the query indices bymi. - Keep a pointer into the sorted
nums. For each query in that order, insert every number<= miinto a 30-level binary trie (10^9 < 2^30). - If nothing has been inserted, the answer is -1.
- Otherwise walk from bit 29 down: at each level go to the child holding the opposite of
xi's bit if it exists (that bit of the XOR becomes 1), else the other child. The bits collected form the answer. - Store each answer at its original query index.
Why it works
After the insertions the trie contains precisely the numbers allowed by the current query. The greedy walk is optimal because a 1 in a higher XOR bit outweighs every lower bit combined, so whenever the opposite bit is available taking it can never be beaten.
Complexity
- Time —
O((n + q) · 30 + n log n + q log q) - Space —
O(n · 30)
Pitfalls
- Answers must be returned in the original query order, not the sorted one.
- Use
<= mi, not< mi, when inserting. - Return -1 only when no number is allowed — an allowed number can still give XOR 0.
Reference solution
Python
from typing import List
def maximizeXor(nums: List[int], queries: List[List[int]]) -> List[int]:
srt = sorted(nums)
order = sorted(range(len(queries)), key=lambda i: queries[i][1])
ch = [0] * ((len(srt) * 30 + 2) * 2)
nodes = 1
p = 0
ans = [0] * len(queries)
for qi in order:
x, m = queries[qi]
while p < len(srt) and srt[p] <= m:
node = 0
v = srt[p]
for b in range(29, -1, -1):
bit = (v >> b) & 1
if not ch[node * 2 + bit]:
ch[node * 2 + bit] = nodes
nodes += 1
node = ch[node * 2 + bit]
p += 1
if p == 0:
ans[qi] = -1
continue
cur = 0
best = 0
for b in range(29, -1, -1):
want = ((x >> b) & 1) ^ 1
if ch[cur * 2 + want]:
best |= 1 << b
cur = ch[cur * 2 + want]
else:
cur = ch[cur * 2 + (want ^ 1)]
ans[qi] = best
return ansJava
public static int[] maximizeXor(int[] nums, int[][] queries) {
int[] srt = nums.clone();
Arrays.sort(srt);
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]));
int[] ch = new int[(srt.length * 30 + 2) * 2];
int nodes = 1, p = 0;
int[] ans = new int[q];
for (int t = 0; t < q; t++) {
int qi = order[t], x = queries[qi][0], m = queries[qi][1];
while (p < srt.length && srt[p] <= m) {
int node = 0;
for (int b = 29; b >= 0; b--) {
int bit = (srt[p] >> b) & 1;
if (ch[node * 2 + bit] == 0) ch[node * 2 + bit] = nodes++;
node = ch[node * 2 + bit];
}
p++;
}
if (p == 0) { ans[qi] = -1; continue; }
int cur = 0, best = 0;
for (int b = 29; b >= 0; b--) {
int want = ((x >> b) & 1) ^ 1;
if (ch[cur * 2 + want] != 0) { best |= 1 << b; cur = ch[cur * 2 + want]; }
else cur = ch[cur * 2 + (want ^ 1)];
}
ans[qi] = best;
}
return ans;
}C++
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> srt(nums);
sort(srt.begin(), srt.end());
int q = queries.size();
vector<int> order(q);
for (int i = 0; i < q; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return queries[a][1] < queries[b][1]; });
vector<int> ch(((int)srt.size() * 30 + 2) * 2, 0);
int nodes = 1, p = 0;
vector<int> ans(q);
for (int t = 0; t < q; t++) {
int qi = order[t], x = queries[qi][0], m = queries[qi][1];
while (p < (int)srt.size() && srt[p] <= m) {
int node = 0;
for (int b = 29; b >= 0; b--) {
int bit = (srt[p] >> b) & 1;
if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
node = ch[node * 2 + bit];
}
p++;
}
if (p == 0) { ans[qi] = -1; continue; }
int cur = 0, best = 0;
for (int b = 29; b >= 0; b--) {
int want = ((x >> b) & 1) ^ 1;
if (ch[cur * 2 + want]) { best |= 1 << b; cur = ch[cur * 2 + want]; }
else cur = ch[cur * 2 + (want ^ 1)];
}
ans[qi] = best;
}
return ans;
}JavaScript
var maximizeXor = function(nums, queries) {
var srt = nums.slice().sort(function(a, b) { return a - b; });
var order = [];
for (var i = 0; i < queries.length; i++) order.push(i);
order.sort(function(a, b) { return queries[a][1] - queries[b][1]; });
var ch = new Int32Array((srt.length * 30 + 2) * 2);
var nodes = 1, p = 0;
var ans = new Array(queries.length);
for (var t = 0; t < order.length; t++) {
var qi = order[t], x = queries[qi][0], m = queries[qi][1];
while (p < srt.length && srt[p] <= m) {
var node = 0;
for (var b = 29; b >= 0; b--) {
var bit = (srt[p] >> b) & 1;
if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
node = ch[node * 2 + bit];
}
p++;
}
if (p === 0) { ans[qi] = -1; continue; }
var cur = 0, best = 0;
for (var b2 = 29; b2 >= 0; b2--) {
var want = ((x >> b2) & 1) ^ 1;
if (ch[cur * 2 + want]) { best |= 1 << b2; cur = ch[cur * 2 + want]; }
else cur = ch[cur * 2 + (want ^ 1)];
}
ans[qi] = best;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms