Practice › Trie
Maximum XOR of Two Numbers
Medium · Trie · Asked at Google, Amazon, Microsoft, Codenation
Print the maximum value of a[i] XOR a[j] over all pairs 0 ≤ i < j < n.
Input
First line: n. Second line: n integers.
Output
The maximum XOR.
Constraints
- 2 ≤ n ≤ 10^5
- 0 ≤ a[i] < 2^31
A binary trie of the numbers (from bit 30 down). For each number, greedily walk toward the opposite bit at every level.
Example 1
Input
6 3 10 5 25 2 8
Output
28
Example 2
Input
2 0 0
Output
0
Hints
- XOR is maximised bit by bit from the top: a 1 in a higher bit beats everything below it.
- Insert numbers into a binary trie (bit 30 down to 0). For each number, walk down preferring the child with the opposite bit.
Approach
Process the numbers in order. Before inserting a[i], query the trie (which holds a[0..i−1]): at each bit, if the child with the opposite bit exists, go there and set that bit in the result; otherwise follow the same bit. This finds the best partner among earlier numbers, so every pair i < j is considered once. Then insert a[i].
Complexity: O(31 · n) time · O(31 · n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<array<int, 2>> t(1, {-1, -1});
auto insert = [&](long long x) {
int cur = 0;
for (int b = 30; b >= 0; b--) {
int bit = (x >> b) & 1;
if (t[cur][bit] < 0) {
t[cur][bit] = t.size();
t.push_back({-1, -1});
}
cur = t[cur][bit];
}
};
long long best = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (i > 0) {
int cur = 0;
long long res = 0;
for (int b = 30; 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];
}
best = max(best, res);
}
insert(x);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : 1 + data[0]]
zero, one = [-1], [-1] # child arrays of the binary trie
best = 0
for i, x in enumerate(a):
if i:
cur, res = 0, 0
for b in range(30, -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]
best = max(best, res)
cur = 0
for b in range(30, -1, -1):
kids = one if (x >> b) & 1 else zero
if kids[cur] == -1:
kids[cur] = len(zero)
zero.append(-1)
one.append(-1)
cur = kids[cur]
print(best)Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
StringTokenizer st = new StringTokenizer(br.readLine());
int[][] t = new int[31 * n + 2][2];
for (int[] row : t) Arrays.fill(row, -1);
int size = 1;
long best = 0;
for (int i = 0; i < n; i++) {
long x = Long.parseLong(st.nextToken());
if (i > 0) {
int cur = 0;
long res = 0;
for (int b = 30; b >= 0; b--) {
int bit = (int) ((x >> b) & 1);
if (t[cur][1 - bit] >= 0) { res |= 1L << b; cur = t[cur][1 - bit]; }
else cur = t[cur][bit];
}
best = Math.max(best, res);
}
int cur = 0;
for (int b = 30; b >= 0; b--) {
int bit = (int) ((x >> b) & 1);
if (t[cur][bit] < 0) t[cur][bit] = size++;
cur = t[cur][bit];
}
}
System.out.println(best);
}
}Solve Maximum XOR of Two Numbers online · All practice problems