Count Pairs With XOR in a Range

Hard
1326.

Count Pairs With XOR in a Range

Count Pairs With XOR in a Range is a hard coding problem on arrays, bit manipulation and trie, asked in Amazon and Google interviews.

Given an integer array nums and two integers low and high, a nice pair is a pair of indices (i, j) with 0 <= i < j < nums.length such that low <= (nums[i] XOR nums[j]) <= high.

Return the number of nice pairs.

Example 1

Input
nums = [5,1,2,6], low = 3, high = 7
Output
6
Explanation
The six XORs are 4, 7, 3, 3, 7 and 4 — all inside `[3, 7]`.

Example 2

Input
nums = [9,8,4,2,1], low = 5, high = 14
Output
8
Explanation
Only `9 XOR 8 = 1` and `2 XOR 1 = 3` fall below 5.

Example 3

Input
nums = [7], low = 1, high = 5
Output
0

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 2 * 10^4
  • 1 <= low <= high <= 2 * 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var countPairs = function(nums, low, high) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Pairs With XOR in a Range — Problem & Solution

Count Pairs With XOR in a Range solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count Pairs With XOR in a Range is a hard coding problem on arrays, bit manipulation and trie, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Bit Manipulation, Trie
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array nums and two integers low and high, a nice pair is a pair of indices (i, j) with 0 <= i < j < nums.length such that low <= (nums[i] XOR nums[j]) <= high.

Return the number of nice pairs.

Example 1

Input: nums = [5,1,2,6], low = 3, high = 7
Output: 6
Explanation: The six XORs are 4, 7, 3, 3, 7 and 4 — all inside `[3, 7]`.

Example 2

Input: nums = [9,8,4,2,1], low = 5, high = 14
Output: 8
Explanation: Only `9 XOR 8 = 1` and `2 XOR 1 = 3` fall below 5.

Example 3

Input: nums = [7], low = 1, high = 5
Output: 0

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= nums[i] <= 2 * 10^4
  • 1 <= low <= high <= 2 * 10^4

Hints for Count Pairs With XOR in a Range

  1. Hint 1

    Counting pairs with XOR in [low, high] equals (pairs with XOR < high + 1) minus (pairs with XOR < low).

  2. Hint 2

    To count earlier numbers y with x XOR y < limit, walk a binary trie of the earlier numbers from the top bit, following limit's bits.

  3. Hint 3

    Where limit has a 1, every y that makes this XOR bit 0 is already smaller — add that whole subtree's count, then continue down the branch that makes the bit 1.

How to solve Count Pairs With XOR in a Range

Turn the range into two "strictly less than" counts and answer each with a binary trie that stores how many inserted numbers pass through every node.

Approach

  1. Keep a binary trie over 15 bits (values stay below 2^15) where each node stores how many inserted numbers pass through it.
  2. For each x in order, add below(x, high + 1) - below(x, low) to the answer, then insert x.
  3. below(x, limit) walks from bit 14 to bit 0. Let xb be x's bit. If limit has a 1 there, every number on the xb child makes the XOR bit 0 and is smaller — add that child's count — and continue into the 1 - xb child. If limit has a 0, continue into the xb child. Stop when the child is missing.

Why it works

Two numbers compare by their first differing bit from the top. Along the walk the XOR so far equals limit's prefix; at a 1-bit of limit, choosing XOR bit 0 makes the XOR smaller regardless of the lower bits, so the whole subtree counts, while XOR bit 1 keeps it tied. At a 0-bit of limit the XOR bit must be 0 to stay tied. Reaching the bottom while tied means XOR equals limit, which is not counted. Inserting after querying counts each pair once.

Complexity

  • Time — O(n · 15)
  • Space — O(n · 15)

Pitfalls

  • Use high + 1 and low as the two strict limits; mixing inclusive and exclusive bounds is the usual off-by-one.
  • Query before inserting, or a number pairs with itself.
  • The trie must cover 15 bits: high + 1 can be 20,001, above 2^14.

Reference solution

Python

from typing import List

def countPairs(nums: List[int], low: int, high: int) -> int:
    size = len(nums) * 15 + 2
    ch = [0] * (size * 2)
    cnt = [0] * size

    def below(x, limit):
        node = 0
        res = 0
        for b in range(14, -1, -1):
            xb = (x >> b) & 1
            if (limit >> b) & 1:
                same = ch[node * 2 + xb]
                if same:
                    res += cnt[same]
                node = ch[node * 2 + (xb ^ 1)]
            else:
                node = ch[node * 2 + xb]
            if not node:
                return res
        return res

    nodes = 1
    total = 0
    for v in nums:
        total += below(v, high + 1) - below(v, low)
        node = 0
        for b in range(14, -1, -1):
            bit = (v >> b) & 1
            if not ch[node * 2 + bit]:
                ch[node * 2 + bit] = nodes
                nodes += 1
            node = ch[node * 2 + bit]
            cnt[node] += 1
    return total

Java

public static int countPairs(int[] nums, int low, int high) {
    int size = nums.length * 15 + 2;
    int[] ch = new int[size * 2];
    int[] cnt = new int[size];
    int nodes = 1;
    int total = 0;
    for (int v : nums) {
        total += cpxBelow(ch, cnt, v, high + 1) - cpxBelow(ch, cnt, v, low);
        int node = 0;
        for (int b = 14; b >= 0; b--) {
            int bit = (v >> b) & 1;
            if (ch[node * 2 + bit] == 0) ch[node * 2 + bit] = nodes++;
            node = ch[node * 2 + bit];
            cnt[node]++;
        }
    }
    return total;
}

static int cpxBelow(int[] ch, int[] cnt, int x, int limit) {
    int node = 0, res = 0;
    for (int b = 14; b >= 0; b--) {
        int xb = (x >> b) & 1;
        if (((limit >> b) & 1) == 1) {
            int same = ch[node * 2 + xb];
            if (same != 0) res += cnt[same];
            node = ch[node * 2 + (xb ^ 1)];
        } else {
            node = ch[node * 2 + xb];
        }
        if (node == 0) return res;
    }
    return res;
}

C++

static int cpxBelow(const vector<int>& ch, const vector<int>& cnt, int x, int limit) {
    int node = 0, res = 0;
    for (int b = 14; b >= 0; b--) {
        int xb = (x >> b) & 1;
        if ((limit >> b) & 1) {
            int same = ch[node * 2 + xb];
            if (same) res += cnt[same];
            node = ch[node * 2 + (xb ^ 1)];
        } else {
            node = ch[node * 2 + xb];
        }
        if (!node) return res;
    }
    return res;
}

int countPairs(vector<int>& nums, int low, int high) {
    int size = (int)nums.size() * 15 + 2;
    vector<int> ch(size * 2, 0), cnt(size, 0);
    int nodes = 1, total = 0;
    for (int v : nums) {
        total += cpxBelow(ch, cnt, v, high + 1) - cpxBelow(ch, cnt, v, low);
        int node = 0;
        for (int b = 14; b >= 0; b--) {
            int bit = (v >> b) & 1;
            if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
            node = ch[node * 2 + bit];
            cnt[node]++;
        }
    }
    return total;
}

JavaScript

var countPairs = function(nums, low, high) {
    var size = nums.length * 15 + 2;
    var ch = new Int32Array(size * 2);
    var cnt = new Int32Array(size);
    var nodes = 1;
    function below(x, limit) {
        var node = 0, res = 0;
        for (var b = 14; b >= 0; b--) {
            var xb = (x >> b) & 1;
            if ((limit >> b) & 1) {
                var same = ch[node * 2 + xb];
                if (same) res += cnt[same];
                node = ch[node * 2 + (xb ^ 1)];
            } else {
                node = ch[node * 2 + xb];
            }
            if (!node) return res;
        }
        return res;
    }
    var total = 0;
    for (var i = 0; i < nums.length; i++) {
        total += below(nums[i], high + 1) - below(nums[i], low);
        var node = 0;
        for (var b = 14; b >= 0; b--) {
            var bit = (nums[i] >> b) & 1;
            if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
            node = ch[node * 2 + bit];
            cnt[node]++;
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation