Practice › Trie
Maximum XOR with a Limit
Hard · Trie · Asked at Google, Amazon, Uber
For each query (x, m), print the maximum of x XOR a[j] over all array elements with a[j] ≤ m. If no element is ≤ m, print -1.
Input
First line: n q. Second line: n integers. Next q lines: x m.
Output
q lines, one answer per query.
Constraints
- 1 ≤ n, q ≤ 10^5
- 0 ≤ a[j], x, m ≤ 10^9
Answer the queries offline in increasing order of m: sort the array, insert elements ≤ m into a binary trie, then query it greedily.
Example 1
Input
5 3 0 1 2 3 4 3 1 1 3 5 6
Output
3 3 7
Example 2
Input
5 3 5 2 4 6 6 12 4 8 1 6 3
Output
14 -1 4
Hints
- Answering each query against the whole array ignores the limit m. Answer the queries offline, sorted by m.
- Sort the array. Before answering a query with limit m, insert every element ≤ m into a binary trie; then do the usual greedy max-XOR query (or −1 if nothing was inserted).
Approach
Sort the elements ascending and the queries by m (remember original indices). Keep a pointer into the sorted array: for each query in increasing m, insert all elements ≤ m into a binary trie. If the trie is still empty, the answer is −1; otherwise walk it from bit 29 down, preferring the opposite bit of x. Write each answer back to its original position. Values ≤ 10^9 < 2^30.
Complexity: O((n + q) · 30 + n log n + q log q) time · O(30 · n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
vector<array<long long, 3>> qs(q); // m, x, index
for (int i = 0; i < q; i++) cin >> qs[i][1] >> qs[i][0], qs[i][2] = i;
sort(qs.begin(), qs.end());
vector<array<int, 2>> t(1, {-1, -1});
vector<long long> ans(q);
int p = 0;
for (auto &qu : qs) {
long long m = qu[0], x = qu[1];
while (p < n && a[p] <= m) {
int cur = 0;
for (int b = 29; b >= 0; b--) {
int bit = (a[p] >> b) & 1;
if (t[cur][bit] < 0) {
t[cur][bit] = t.size();
t.push_back({-1, -1});
}
cur = t[cur][bit];
}
p++;
}
if (p == 0) {
ans[qu[2]] = -1;
continue;
}
int cur = 0;
long long res = 0;
for (int b = 29; b >= 0; b--) {
int bit = (x >> b) & 1;
if (t[cur][!bit] >= 0) res |= 1LL << b, cur = t[cur][!bit];
else cur = t[cur][bit];
}
ans[qu[2]] = res;
}
for (long long v : ans) cout << v << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, q = data[0], data[1]
a = sorted(data[2 : 2 + n])
qs = sorted((data[3 + n + 2 * i], data[2 + n + 2 * i], i) for i in range(q)) # (m, x, index)
zero, one = [-1], [-1]
ans, p = [0] * q, 0
for m, x, idx in qs:
while p < n and a[p] <= m:
cur, v = 0, a[p]
for b in range(29, -1, -1):
kids = one if (v >> b) & 1 else zero
if kids[cur] == -1:
kids[cur] = len(zero)
zero.append(-1)
one.append(-1)
cur = kids[cur]
p += 1
if p == 0:
ans[idx] = -1
continue
cur = res = 0
for b in range(29, -1, -1):
bit = (x >> b) & 1
want = one[cur] if bit == 0 else zero[cur]
if want != -1:
res |= 1 << b
cur = want
else:
cur = zero[cur] if bit == 0 else one[cur]
ans[idx] = res
print("\n".join(map(str, ans)))Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int q = (int) in.nval;
long[] a = new long[n];
for (int i = 0; i < n; i++) { in.nextToken(); a[i] = (long) in.nval; }
Arrays.sort(a);
long[][] qs = new long[q][3];
for (int i = 0; i < q; i++) {
in.nextToken();
qs[i][1] = (long) in.nval;
in.nextToken();
qs[i][0] = (long) in.nval;
qs[i][2] = i;
}
Arrays.sort(qs, (u, v) -> Long.compare(u[0], v[0]));
int[][] t = new int[30 * n + 2][2];
for (int[] row : t) Arrays.fill(row, -1);
int size = 1, p = 0;
long[] ans = new long[q];
for (long[] qu : qs) {
while (p < n && a[p] <= qu[0]) {
int cur = 0;
for (int b = 29; b >= 0; b--) {
int bit = (int) ((a[p] >> b) & 1);
if (t[cur][bit] < 0) t[cur][bit] = size++;
cur = t[cur][bit];
}
p++;
}
if (p == 0) {
ans[(int) qu[2]] = -1;
continue;
}
int cur = 0;
long res = 0;
for (int b = 29; b >= 0; b--) {
int bit = (int) ((qu[1] >> b) & 1);
if (t[cur][1 - bit] >= 0) { res |= 1L << b; cur = t[cur][1 - bit]; }
else cur = t[cur][bit];
}
ans[(int) qu[2]] = res;
}
StringBuilder sb = new StringBuilder();
for (long v : ans) sb.append(v).append('\n');
System.out.print(sb);
}
}Solve Maximum XOR with a Limit online · All practice problems