Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. XOR is maximised bit by bit from the top: a 1 in a higher bit beats everything below it.
  2. 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