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^41 <= nums[i] <= 2 * 10^41 <= low <= high <= 2 * 10^4
Hints for Count Pairs With XOR in a Range
Hint 1
Counting pairs with XOR in
[low, high]equals (pairs with XOR< high + 1) minus (pairs with XOR< low).Hint 2
To count earlier numbers
ywithx XOR y < limit, walk a binary trie of the earlier numbers from the top bit, followinglimit's bits.Hint 3
Where
limithas a 1, everyythat 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
- Keep a binary trie over 15 bits (values stay below 2^15) where each node stores how many inserted numbers pass through it.
- For each
xin order, addbelow(x, high + 1) - below(x, low)to the answer, then insertx. below(x, limit)walks from bit 14 to bit 0. Letxbbe x's bit. Iflimithas a 1 there, every number on thexbchild makes the XOR bit 0 and is smaller — add that child's count — and continue into the1 - xbchild. Iflimithas a 0, continue into thexbchild. 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 + 1andlowas 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 + 1can 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 totalJava
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