Trie — Count Pairs With XOR in a Range

↗ LeetCode: Count Pairs With XOR in a Range · Hard · pattern chapter →

Asked atGoogleAmazon

Count pairs (i, j) with i < j and low ≤ nums[i] XOR nums[j] ≤ high.

Example 1 — nums=[1,4,2,7], low=2, high=6 → 6Example 2 — nums=[9,8,4,2,1], low=5, high=14 → 8

Constraints — 1 ≤ n ≤ 2·10⁴; 0 ≤ nums[i] ≤ 2·10⁴. Brute enumerates every pair XOR — O(n²) = 4·10⁸ ops at n=2·10⁴ (TLE). Bit-trie + range decomposition is O(n·30·2) = ~10⁶ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — All pairs

O(n²). Baseline; borderline TLE.

Approach 2 — Binary trie with subtree counts (canonical)

Insight. count(≤ high) - count(≤ low - 1). For each nums[i], count how many previously-inserted values yield XOR ≤ threshold via a per-bit analysis.

java

class Node { Node[] c = new Node[2]; int cnt; }
int countPairs(int[] nums, int low, int high) {
    return countLE(nums, high) - countLE(nums, low - 1);
}
int countLE(int[] nums, int t) {
    Node root = new Node();
    int total = 0;
    for (int x : nums) { total += queryLE(root, x, t); insert(root, x); }
    return total;
}
void insert(Node root, int x) {
    Node cur = root;
    for (int i = 15; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (cur.c[b] == null) cur.c[b] = new Node();
        cur = cur.c[b]; cur.cnt++;
    }
}
int queryLE(Node root, int x, int t) {
    Node cur = root; int r = 0;
    for (int i = 15; i >= 0; i--) {
        if (cur == null) return r;
        int xb = (x >> i) & 1, tb = (t >> i) & 1;
        if (tb == 1) {
            if (cur.c[xb] != null) r += cur.c[xb].cnt;
            cur = cur.c[1 - xb];
        } else cur = cur.c[xb];
    }
    if (cur != null) r += cur.cnt;
    return r;
}

Execution Trace

All pairs

Step 1 / 3Initialize scan.

Complexity — Time O(n · 16); Space O(n · 16).

Try it yourself

Complexity summary

Approach	Time	Space	Grade
All pairs	O(n²)	O(1)	baseline
Binary trie counting	O(n · 16)	O(n · 16)	canonical

When to use which

XOR count in a range → binary trie with subtree counts.
Fixed range not variable → single sweep suffices.
Streaming → same trie, insert online.

✨AI Study CompanionBeta

Was this page helpful?

Trie — Count Pairs With XOR in a Range ​

Approach 1 — All pairs ​

Approach 2 — Binary trie with subtree counts (canonical) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​