Count Pairs With XOR in a Range solution and explanation
9 more videos on this problem
Count Pairs With Xor In A Range | Leetcode 1803Pepcoding · 56:01 · 5K views
LeetCode 1803. Count Pairs With XOR in a RangeHappy Coding · 32:27 · 2K views
【每日一题】1803. Count Pairs With XOR in a Range, 3/23/2021Huifeng Guan · 59:36 · 701 views
1803. Count Pairs With XOR in a Range (Leetcode Hard)Programming Live with Larry · 48:18 · 567 views
LeetCode 1803. Count Pairs With XOR in a Range | Weekly Contest 233宰相小甘罗 · 7:57 · 537 views
LeetCode 1803. Count Pairs With XOR in a Range 中文 | Weekly Contest 233宰相小甘罗 · 6:20 · 302 views
Count Pairs With XOR in a RangePerfectAlgos · 23:58 · 263 views
Count Pairs With Xor In A Range | Module : Tries | In Hindi | CPP | Video_2Pepcoding · 55:11 · 254 views
Leetcode 1803. Count Pairs With XOR in a RangeFearless Learner · 5:04 · 163 views
Count Pairs With Xor In A Range | Module : Tries | In English | CPP | Video_2Pepcoding · 1:05:23 · 92 views
The problem
Given a (0-indexed) integer array nums and two integers low and high, return the number of nice pairs.
A nice pair is a pair (i, j) where 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <= high.
Example 1:
Input: nums = [1,4,2,7], low = 2, high = 6
Output: 6
Explanation: All nice pairs (i, j) are as follows:
- (0, 1): nums[0] XOR nums[1] = 5
- (0, 2): nums[0] XOR nums[2] = 3
- (0, 3): nums[0] XOR nums[3] = 6
- (1, 2): nums[1] XOR nums[2] = 6
- (1, 3): nums[1] XOR nums[3] = 3
- (2, 3): nums[2] XOR nums[3] = 5
Example 2:
Input: nums = [9,8,4,2,1], low = 5, high = 14 Output: 8 Explanation: All nice pairs (i, j) are as follows: - (0, 2): nums[0] XOR nums[2] = 13 - (0, 3): nums[0] XOR nums[3] = 11 - (0, 4): nums[0] XOR nums[4] = 8 - (1, 2): nums[1] XOR nums[2] = 12 - (1, 3): nums[1] XOR nums[3] = 10 - (1, 4): nums[1] XOR nums[4] = 9 - (2, 3): nums[2] XOR nums[3] = 6 - (2, 4): nums[2] XOR nums[4] = 5
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i] <= 2 * 1041 <= low <= high <= 2 * 104
Approach overview
Problem Overview: You are given an integer array nums and two values low and high. The task is to count pairs (i, j) where i < j and the XOR of the pair nums[i] ^ nums[j] lies within the range [low, high]. A direct comparison of every pair works but becomes too slow for large inputs.
Approach 1: Brute Force Pair Enumeration (O(n²) time, O(1) space)
The simplest solution checks every pair in the array. Iterate with two nested loops, compute x = nums[i] ^ nums[j], and increment the answer if low ≤ x ≤ high. XOR is a constant-time bit operation, so the main cost comes from examining all n(n−1)/2 pairs. This approach works well for small arrays and helps validate correctness during debugging. However, for large inputs the quadratic complexity becomes the bottleneck.
Approach 2: Bitwise Trie with Range Counting (O(n · B) time, O(n · B) space)
The optimized method uses a binary Trie to count how many previous numbers produce a valid XOR with the current number. Instead of directly counting XOR values inside [low, high], compute:
count(xor ≤ high) − count(xor < low).
Insert numbers into a bitwise Trie while iterating through the array. Each node represents a bit (0 or 1). For a number num, traverse the Trie from the most significant bit to the least. At each level, use the bit of num and the corresponding bit of the limit (high or low−1) to decide whether entire branches can be counted or must be explored further. This pruning works because XOR results depend only on bit differences.
If the current limit bit is 1, you can add the count of nodes that keep the XOR bit smaller and continue exploring the alternative branch. If the limit bit is 0, you must stay on the branch that keeps the XOR result within the constraint. The Trie stores counts of numbers passing through each node, making it possible to accumulate valid pair counts efficiently.
This technique processes each number in about B steps, where B is the number of bits (usually 15–16 for this problem). It reduces the complexity from quadratic to near-linear while maintaining deterministic performance.
The solution relies heavily on bit manipulation and a binary Trie structure applied over an array. The key insight is converting a range query into two prefix counts.
Recommended for interviews: Start by explaining the brute force method to demonstrate understanding of the XOR condition. Then transition to the Trie-based counting strategy. Interviewers typically expect the optimized approach because it shows comfort with bitwise reasoning, prefix counting, and specialized data structures.
Approach 1: Brute Force Approach
This approach involves checking every possible pair (i, j) strictly where i < j, calculating their XOR, and checking if the result lies within the given range [low, high].
def count_nice_pairs(nums, low, high):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
xor_value = nums[i] ^ nums[j]
if low <= xor_value <= high:
count += 1
return count
nums = [1, 4, 2, 7]
low = 2
high = 6
print(count_nice_pairs(nums, low, high))public class Solution {
public static int countNicePairs(int[] nums, int low, int high) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int xorValue = nums[i] ^ nums[j];
if (xorValue >= low && xorValue <= high) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {1, 4, 2, 7};
int low = 2, high = 6;
System.out.println(countNicePairs(nums, low, high));
}
}#include <iostream>
#include <vector>
int countNicePairs(const std::vector<int>& nums, int low, int high) {
int count = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int xorValue = nums[i] ^ nums[j];
if (xorValue >= low && xorValue <= high) {
count++;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {1, 4, 2, 7};
int low = 2, high = 6;
std::cout << countNicePairs(nums, low, high) << std::endl;
return 0;
}function countNicePairs(nums, low, high) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
let xorValue = nums[i] ^ nums[j];
if (xorValue >= low && xorValue <= high) {
count++;
}
}
}
return count;
}
const nums = [1, 4, 2, 7];
const low = 2, high = 6;
console.log(countNicePairs(nums, low, high));#include <stdio.h>
int countNicePairs(int* nums, int numsSize, int low, int high) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
int xorValue = nums[i] ^ nums[j];
if (xorValue >= low && xorValue <= high) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {1, 4, 2, 7};
int low = 2, high = 6;
int result = countNicePairs(nums, sizeof(nums)/sizeof(nums[0]), low, high);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public static int CountNicePairs(int[] nums, int low, int high) {
int count = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int xorValue = nums[i] ^ nums[j];
if (xorValue >= low && xorValue <= high) {
count++;
}
}
}
return count;
}
static void Main(string[] args) {
int[] nums = {1, 4, 2, 7};
int low = 2, high = 6;
Console.WriteLine(CountNicePairs(nums, low, high));
}
}This Python solution checks each pair of indices i and j such that i < j, calculates their XOR, and counts how many hold in the required range.
Time Complexity: O(n^2), Space Complexity: O(1).
Approach 2: Optimized Bit-Operation Approach Using Trie
This approach involves building a Trie where each path represents a binary number in the array. Using the properties of XOR, we can efficiently count nice pairs by traversing this Trie.
class TrieNode:
def __init__(self):
self.children = [None, None]
self.count = 0
class Solution:
MAX_BITS = 14 # maximum bits for numbers less than 20000
def countPairsWithXorInRange(self, nums, low, high):
root = TrieNode()
def insert(num):
node = root
for i in range(self.MAX_BITS, -1, -1):
bit = (num >> i) & 1
if not node.children[bit]:
node.children[bit] = TrieNode()
node = node.children[bit]
node.count += 1
def query(num, limit):
node = root
result = 0
for i in range(self.MAX_BITS, -1, -1):
if not node:
break
bit_num = (num >> i) & 1
bit_limit = (limit >> i) & 1
if bit_limit:
if node.children[bit_num]:
result += node.children[bit_num].count
node = node.children[1 - bit_num]
else:
node = node.children[bit_num]
return result
total_pairs = 0
for num in nums:
total_pairs += query(num, high + 1) - query(num, low)
insert(num)
return total_pairs
nums = [1, 4, 2, 7]
low = 2
high = 6
solution = Solution()
print(solution.countPairsWithXorInRange(nums, low, high))class TrieNode {
TrieNode[] children = new TrieNode[2];
int count = 0;
}
class Solution {
static final int MAX_BITS = 14; // because 2^14 > 20000
public int countPairsWithXorInRange(int[] nums, int low, int high) {
TrieNode root = new TrieNode();
int count = 0;
for (int num : nums) {
count += query(root, num, high + 1) - query(root, num, low);
insert(root, num);
}
return count;
}
private void insert(TrieNode root, int num) {
TrieNode curr = root;
for (int i = MAX_BITS; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[bit] == null) {
curr.children[bit] = new TrieNode();
}
curr = curr.children[bit];
curr.count++;
}
}
private int query(TrieNode root, int num, int limit) {
TrieNode curr = root;
int result = 0;
for (int i = MAX_BITS; i >= 0; i--) {
int bitNum = (num >> i) & 1;
int bitLim = (limit >> i) & 1;
if (bitLim == 1) {
if (curr.children[bitNum] != null) {
result += curr.children[bitNum].count;
}
curr = curr.children[1 - bitNum];
} else {
curr = curr.children[bitNum];
}
if (curr == null) break;
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 4, 2, 7};
int low = 2, high = 6;
System.out.println(sol.countPairsWithXorInRange(nums, low, high));
}
}#include <iostream>
#include <vector>
using namespace std;
class TrieNode {
public:
TrieNode* children[2] = {nullptr, nullptr};
int count = 0;
};
class Solution {
const int MAX_BITS = 14; // because 2^14 > 20000
void insert(TrieNode* root, int num) {
TrieNode* node = root;
for (int i = MAX_BITS; i >= 0; --i) {
int bit = (num >> i) & 1;
if (!node->children[bit])
node->children[bit] = new TrieNode();
node = node->children[bit];
node->count++;
}
}
int query(TrieNode* root, int num, int limit) {
TrieNode* node = root;
int ans = 0;
for (int i = MAX_BITS; i >= 0; --i) {
int bitNum = (num >> i) & 1;
int bitLim = (limit >> i) & 1;
if (bitLim) {
if (node->children[bitNum])
ans += node->children[bitNum]->count;
node = node->children[1 - bitNum];
} else {
node = node->children[bitNum];
}
if (!node) break;
}
return ans;
}
public:
int countPairsWithXorInRange(vector<int>& nums, int low, int high) {
TrieNode* root = new TrieNode();
int count = 0;
for (int num : nums) {
count += query(root, num, high + 1) - query(root, num, low);
insert(root, num);
}
return count;
}
};
int main() {
Solution sol;
vector<int> nums = {1, 4, 2, 7};
int low = 2, high = 6;
cout << sol.countPairsWithXorInRange(nums, low, high) << endl;
return 0;
}class TrieNode {
constructor() {
this.children = [null, null];
this.count = 0;
}
}
function countPairsWithXorInRange(nums, low, high) {
const MAX_BITS = 14;
const root = new TrieNode();
function insert(num) {
let node = root;
for (let i = MAX_BITS; i >= 0; --i) {
const bit = (num >> i) & 1;
if (!node.children[bit]) {
node.children[bit] = new TrieNode();
}
node = node.children[bit];
node.count++;
}
}
function query(num, limit) {
let node = root;
let result = 0;
for (let i = MAX_BITS; i >= 0; --i) {
const bitNum = (num >> i) & 1;
const bitLim = (limit >> i) & 1;
if (node === null) break;
if (bitLim === 1) {
if (node.children[bitNum]) {
result += node.children[bitNum].count;
}
node = node.children[1 - bitNum];
} else {
node = node.children[bitNum];
}
}
return result;
}
let totalPairs = 0;
for (const num of nums) {
totalPairs += query(num, high + 1) - query(num, low);
insert(num);
}
return totalPairs;
}
const nums = [1, 4, 2, 7];
const low = 2, high = 6;
console.log(countPairsWithXorInRange(nums, low, high));#include <stdio.h>
#include <stdlib.h>
#define MAX_BITS 14 // As nums[i] can be at max 20000, there's no need for more than 15 bits
typedef struct TrieNode {
struct TrieNode* children[2];
int count;
} TrieNode;
TrieNode* createNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->children[0] = NULL;
node->children[1] = NULL;
node->count = 0;
return node;
}
void insert(TrieNode* root, int num) {
TrieNode* curr = root;
for (int i = MAX_BITS; i >= 0; i--) {
int bit = (num >> i) & 1;
if (!curr->children[bit]) {
curr->children[bit] = createNode();
}
curr = curr->children[bit];
curr->count++;
}
}
int query(TrieNode* root, int num, int limit) {
TrieNode* curr = root;
int result = 0;
for (int i = MAX_BITS; i >= 0; i--) {
int bitNum = (num >> i) & 1;
int bitLim = (limit >> i) & 1;
if (bitLim) {
if (curr->children[bitNum]) result += curr->children[bitNum]->count;
curr = curr->children[1 - bitNum];
} else {
curr = curr->children[bitNum];
}
if (!curr) break;
}
return result;
}
int countPairsWithXorInRange(int* nums, int numsSize, int low, int high) {
TrieNode* root = createNode();
int count = 0;
for (int i = 0; i < numsSize; i++) {
count += query(root, nums[i], high + 1) - query(root, nums[i], low);
insert(root, nums[i]);
}
return count;
}
int main() {
int nums[] = {1, 4, 2, 7};
int low = 2, high = 6;
int result = countPairsWithXorInRange(nums, sizeof(nums)/sizeof(nums[0]), low, high);
printf("%d\n", result);
return 0;
}using System;
class TrieNode {
public TrieNode[] children = new TrieNode[2];
public int count = 0;
}
class Solution {
const int MAX_BITS = 14; // because 2^14 > 20000
public int CountPairsWithXorInRange(int[] nums, int low, int high) {
TrieNode root = new TrieNode();
int count = 0;
foreach (var num in nums) {
count += Query(root, num, high + 1) - Query(root, num, low);
Insert(root, num);
}
return count;
}
private void Insert(TrieNode root, int num) {
TrieNode curr = root;
for (int i = MAX_BITS; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[bit] == null)
curr.children[bit] = new TrieNode();
curr = curr.children[bit];
++curr.count;
}
}
private int Query(TrieNode root, int num, int limit) {
TrieNode curr = root;
int result = 0;
for (int i = MAX_BITS; i >= 0; i--) {
if (curr == null) break;
int bitNum = (num >> i) & 1;
int bitLim = (limit >> i) & 1;
if (bitLim == 1) {
if (curr.children[bitNum] != null)
result += curr.children[bitNum].count;
curr = curr.children[1 - bitNum];
} else {
curr = curr.children[bitNum];
}
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = { 1, 4, 2, 7 };
int low = 2, high = 6;
Console.WriteLine(sol.CountPairsWithXorInRange(nums, low, high));
}
}This Python implementation takes advantage of characterizing numbers as binary paths in Tries. It checks potential XOR values efficiently by establishing a structure that allows binary-tied decisions regarding current numbers and their potentially formed XOR values.
Time Complexity: O(n * 15), Space Complexity: O(n * 15).
Approach 3: 0-1 Trie
For this kind of problem that counts the interval [low, high], we can consider converting it into counting [0, high] and [0, low - 1], and then subtracting the latter from the former to get the answer.
In this problem, we can count how many pairs of numbers have an XOR value less than high+1, and then count how many pairs of numbers have an XOR value less than low. The difference between these two counts is the number of pairs whose XOR value is in the interval [low, high].
Moreover, for array XOR counting problems, we can usually use a "0-1 Trie" to solve them.
The definition of the Trie node is as follows:
children[0]andchildren[1]represent the left and right child nodes of the current node, respectively;cntrepresents the number of numbers ending with the current node.
In the Trie, we also define the following two functions:
One function is insert(x), which inserts the number x into the Trie. This function inserts the number x into the "0-1 Trie" in the order of binary bits from high to low. If the current binary bit is 0, it is inserted into the left child node, otherwise, it is inserted into the right child node. Then the count value cnt of the node is increased by 1.
Another function is search(x, limit), which searches for the count of numbers in the Trie that have an XOR value with x less than limit. This function starts from the root node node of the Trie, traverses the binary bits of x from high to low, and denotes the current binary bit of x as v. If the current binary bit of limit is 1, we can directly add the count value cnt of the child node that has the same binary bit v as x to the answer, and then move the current node to the child node that has a different binary bit v from x, i.e., node = node.children[v ^ 1]. Continue to traverse the next bit. If the current binary bit of limit is 0, we can only move the current node to the child node that has the same binary bit v as x, i.e., node = node.children[v]. Continue to traverse the next bit. After traversing the binary bits of x, return the answer.
With the above two functions, we can solve this problem.
We traverse the array nums. For each number x, we first search in the Trie for the count of numbers that have an XOR value with x less than high+1, and then search in the Trie for the count of pairs that have an XOR value with x less than low, and add the difference between the two counts to the answer. Then insert x into the Trie. Continue to traverse the next number x until the array nums is traversed. Finally, return the answer.
The time complexity is O(n times log M), and the space complexity is O(n times log M). Here, n is the length of the array nums, and M is the maximum value in the array nums. In this problem, we directly take log M = 16.
type Trie struct {
children [2]*Trie
cnt int
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(x int) {
node := this
for i := 15; i >= 0; i-- {
v := (x >> i) & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
node.cnt++
}
}
func (this *Trie) search(x, limit int) (ans int) {
node := this
for i := 15; i >= 0 && node != nil; i-- {
v := (x >> i) & 1
if (limit >> i & 1) == 1 {
if node.children[v] != nil {
ans += node.children[v].cnt
}
node = node.children[v^1]
} else {
node = node.children[v]
}
}
return
}
func countPairs(nums []int, low int, high int) (ans int) {
tree := newTrie()
for _, x := range nums {
ans += tree.search(x, high+1) - tree.search(x, low)
tree.insert(x)
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), Space Complexity: O(1). |
| Optimized Bit-Operation Approach Using Trie | Time Complexity: O(n * 15), Space Complexity: O(n * 15). |
| 0-1 Trie | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n²) | O(1) | Small arrays or when verifying correctness of the XOR condition |
| Bitwise Trie Range Counting | O(n · B) | O(n · B) | Large inputs where efficient pair counting is required; standard optimal interview solution |
Frequently asked questions
Is Count Pairs With XOR in a Range easy or hard?
The problem is classified as Hard because it requires combining XOR properties with a Trie-based counting strategy. Recognizing that a range query can be split into two prefix XOR constraints is the main insight that makes the optimized solution possible.
Count Pairs With XOR in a Range Python/Java solution
In Python or Java, implement a Trie node with two children representing bit 0 and bit 1 plus a counter. For each number, query the Trie for counts of XOR ≤ limit, update the answer, and insert the number into the Trie. This yields an O(n · B) solution.
How to solve Count Pairs With XOR in a Range in O(n)?
Use a binary Trie to store previously processed numbers and count how many produce XOR results within a bound. Each insertion and query processes B bits, making the complexity O(n · B), which behaves close to linear time since B is small and fixed.
What is the best approach for Count Pairs With XOR in a Range?
The optimal solution uses a binary Trie combined with bit manipulation. For each number, count how many previously inserted numbers produce XOR values ≤ high and subtract the count for XOR < low. This converts the range query into two prefix queries and runs in O(n · B) time, where B is the number of bits.
Is Count Pairs With XOR in a Range asked at Google/Amazon/Meta?
Problems combining XOR with Trie-based bit counting appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include maximum XOR pair, XOR with constraints, and prefix XOR queries, all testing bit manipulation and Trie design.
What data structure is used in Count Pairs With XOR in a Range?
The optimized approach uses a binary Trie (also called a bitwise Trie). Each level represents a bit position, and nodes store counts of numbers passing through that branch, allowing efficient counting of numbers that satisfy XOR constraints.
What is the time complexity of Count Pairs With XOR in a Range?
The brute force solution runs in O(n^2) time by checking every pair. The optimized Trie-based method runs in O(n · B), where B is the bit length of the numbers (typically around 15–16). Space complexity for the Trie approach is also O(n · B).