Count Pairs With XOR in a Range
Hard · Tries · Array · Bit Manipulation · Trie
Problem
You are 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 < len(nums) such that low <= nums[i] XOR nums[j] <= high. Return the number of nice pairs.
With 2 · 10^4 numbers there are about 2 · 10^8 pairs, so checking each one is too slow.
Examples
Input: nums = [3,5,6,1], low = 2, high = 5 Output: 4
The pairwise XORs are 6, 5, 2, 3, 4 and 7; four of them (5, 2, 3, 4) lie in [2, 5].
Input: nums = [4,4], low = 1, high = 3 Output: 0
4 XOR 4 = 0, below the range.
Input: nums = [1,2,4], low = 3, high = 6 Output: 3
The XORs are 3, 5 and 6, all in [3, 6].
Constraints
- 1 <= len(nums) <= 2 · 10^4
- 1 <= nums[i] <= 2 · 10^4
- 1 <= low <= high <= 2 · 10^4
Approaches
- Baseline: every pair — time O(n²), space O(1)
Follow-up
Each number costs O(B) for its insert and two queries, with B = 15 bits here. The use cases count pairs whose XOR equals one value exactly, where a hash map is enough, and ask, for every number, how many earlier numbers fall in the range with it.
Related problems
Start free on Cariara · Coding problems · System design studio
