Getting everything ready for you…

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

0s

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

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

  1. Answering each query against the whole array ignores the limit m. Answer the queries offline, sorted by m.
  2. 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