Count Pairs With XOR in a Range

66.2k
0

Given an integer array nums and two integers low and high, return the number of nice pairs.

A pair (i, j) is called nice if:

  • 0 <= i < j < nums.length

  • low <= (nums[i] XOR nums[j]) <= high

Example 1

Input: nums = [1, 4, 2, 7], low = 2, high = 6

Output: 6

Explanation: The valid pairs are:

  • (1, 4) because 1 XOR 4 = 5

  • (1, 2) because 1 XOR 2 = 3

  • (1, 7) because 1 XOR 7 = 6

  • (4, 2) because 4 XOR 2 = 6

  • (4, 7) because 4 XOR 7 = 3

  • (2, 7) because 2 XOR 7 = 5

So, the answer is 6.

Example 2

Input: nums = [9, 8, 4, 2, 1], low = 5, high = 14

Output: 8

Explanation: Among all possible pairs, the pairs (9, 4), (9, 2), (9, 1), (8, 4), (8, 2), (8, 1), (4, 2), and (4, 1) have XOR values of 13, 11, 8, 12, 10, 9, 6, and 5, respectively. All of these values lie within the inclusive range [5, 14]. The remaining pairs, (9, 8) and (2, 1), have XOR values of 1 and 3, which fall outside the required range. Therefore, the total number of valid pairs is 8.

Brute Force Approach

The most direct idea is to try every pair. That works because the problem simply asks for the count of valid pairs, so checking every (i, j) will definitely find the correct answer. The only issue is speed. If the array has n numbers, then there are almost n^2 pairs. That becomes too slow for large inputs.

Algorithm

  • Start with count = 0 because no valid pair has been found yet.

  • Use the first loop to choose the left element of the pair. This is needed so every element gets a chance to pair with the elements after it.

  • Use the second loop from i + 1 onward. This is done so the same pair is not counted twice and an element is not paired with itself.

  • Compute nums[i] XOR nums[j] for the current pair because this XOR value is the only thing that decides whether the pair is valid.

  • Check whether that XOR lies between low and high. This check is needed because only range-valid pairs should increase the answer.

  • If the XOR is valid, increase count by 1.

  • After all pairs are checked, return count because it now stores the number of nice pairs.

Dry Run

Counting Pairs with Xor in a Range Brute Dry Run

Counting Pairs with Xor in a Range Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Counts how many pairs have XOR value
lying inside the range [low, high].
*/
int countPairs(vector<int>& nums, int low, int high) {
// Stores the number of valid pairs found so far.
int count = 0;
// Pick the first element of the pair one by one.
for (int i = 0; i < (int)nums.size(); i++) {
// Pair the current element with only the elements after it
// so each pair is counted exactly once.
for (int j = i + 1; j < (int)nums.size(); j++) {
// Store the XOR value because the range check depends on it.
int currentXor = nums[i] ^ nums[j];
// Count this pair only when its XOR stays inside the required range.
if (currentXor >= low && currentXor <= high) {
count++;
}
}
}
return count;
}
};
// Driver code starts
int main() {
vector<int> nums = {1, 4, 2, 7};
int low = 2;
int high = 6;
Solution obj;
cout << obj.countPairs(nums, low, high) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2), because every pair is checked once.

Space Complexity: O(1), because only a few variables are used.

Optimal Approach

The key observation is that counting XOR values inside a range [low, high] is hard directly, but counting XOR values smaller than a limit is easier.

So instead of counting:

  • pairs with XOR in [low, high]

count this:

  • pairs with XOR < high + 1

  • pairs with XOR < low

Then subtract them. That means: pairs in [low, high] = pairs with XOR < (high + 1) - pairs with XOR < low

Now the next question becomes: how to quickly count how many previous numbers give XOR smaller than a limit with the current number?

A binary trie helps here because XOR is decided bit by bit. If previous numbers are stored in a trie, then for each current number, the count of valid earlier partners can be found by walking through bits from left to right.

Algorithm

  • Define a Trie node structure holding two child pointers for bits 0 and 1, along with a running prefix counter, to represent binary values hierarchically and track how many numbers share any given binary prefix.

  • Fix the bit traversal depth from the most significant bit (bit 15 or 16) down to 0, matching the maximum possible value in the array constraints, to ensure that every compared number aligns at the exact same bit positions for prefix comparisons.

  • Implement an insertion procedure that steps down through the bits of a number, creating missing nodes and incrementing each node's visit count, so that every subtree maintains an accurate tally of all numbers stored beneath it.

  • Reduce the bounded range condition low <= (num_1 xor num_2) <= high to the difference of two strict prefix counts, countLessThan(num,high + 1) - countLessThan(num,low) ,transforming a two-sided range check into standard cumulative prefix counting.

  • Inspect bits strictly from most significant to least significant within countLessThan, since the highest differing bit between two numbers completely determines which value is smaller, rendering all subsequent lower bits irrelevant once a difference appears.

  • Add the count of the matching-bit child branch directly to the running accumulator whenever the limit's current bit is 1, because choosing that branch produces an XOR bit of 0, instantly guaranteeing that every number along that path yields an XOR value strictly smaller than the limit without inspecting deeper bits.

  • Shift traversal pointer down the opposite-bit branch after accumulating the matching branch, because following the branch that produces an XOR bit of 1 keeps the XOR value tied with the limit's prefix, requiring lower bits to determine whether the final result remains strictly smaller.

  • Advance traversal solely down the matching-bit branch without adding to the counter whenever the limit's current bit is 0, because producing an XOR bit of 1 would immediately exceed the limit, while producing an XOR bit of 0 keeps the XOR tied with the limit and requires deeper bit inspection.

  • Halt traversal immediately whenever the required continuation pointer is null, because no previously inserted numbers match the current necessary prefix to continue evaluating valid pairs.

  • Iterate through the array while querying the trie for valid partners before inserting the current number, naturally enforcing the strict index constraint i < j , preventing any number from pairing with itself, and eliminating duplicate pair counting without separate deduplication logic.

  • Accumulate the calculated differences into a global counter and return this sum, yielding the complete count of pairs satisfying the target XOR range in $O(N \cdot B)$ time where $B$ is the fixed bit length.

Key Points

  • Query first, then insert.

  • high + 1 is used because the helper counts XOR values strictly less than the given limit.

  • A fixed bit range up to 15 is enough here because values are at most 20000.

Dry Run

Count Pairs with Xor in a Range Optimal Dry Run

Count Pairs with Xor in a Range Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class TrieNode {
public:
TrieNode* children[2];
int count;
// Creates one trie node with no child path and zero stored numbers yet.
TrieNode() {
children[0] = nullptr;
children[1] = nullptr;
count = 0;
}
};
class Solution {
private:
static const int MAX_BIT = 15;
TrieNode* root;
// Inserts one number into the binary trie.
void insert(int num) {
// Start insertion from the trie root.
TrieNode* node = root;
// Walk from the highest useful bit to the lowest bit
// so the trie path matches the binary form of the number.
for (int bit = MAX_BIT; bit >= 0; bit--) {
// Extract the current bit to choose the next trie branch.
int currentBit = (num >> bit) & 1;
// Create the branch only when this bit path appears for the first time.
if (node->children[currentBit] == nullptr) {
node->children[currentBit] = new TrieNode();
}
// Move deeper because the next lower bit must continue from this prefix.
node = node->children[currentBit];
// Increase the stored count so this node knows one more number uses this path.
node->count++;
}
}
// Counts how many inserted numbers make XOR with num strictly smaller than limit.
int countLessThan(int num, int limit) {
// Start searching from the trie root.
TrieNode* node = root;
// Stores how many previous numbers already satisfy the strict limit condition.
int pairs = 0;
// Compare bits from left to right because higher bits decide the order first.
for (int bit = MAX_BIT; bit >= 0 && node != nullptr; bit--) {
// Extract the current bit of the number being queried.
int currentBit = (num >> bit) & 1;
// Extract the current bit of the limit so the allowed branches can be decided.
int limitBit = (limit >> bit) & 1;
// If the limit bit is 1, taking XOR bit 0 here keeps the result smaller
// at this position, so that whole branch can be counted immediately.
if (limitBit == 1) {
if (node->children[currentBit] != nullptr) {
pairs += node->children[currentBit]->count;
}
// Continue only on the branch that makes XOR bit 1,
// because that branch still needs lower-bit checking.
node = node->children[currentBit ^ 1];
} else {
// If the limit bit is 0, only XOR bit 0 can stay valid so far.
node = node->children[currentBit];
}
}
return pairs;
}
public:
// Creates the trie root once for this solution object.
Solution() {
root = new TrieNode();
}
/*
Counts how many pairs have XOR value
lying inside the range [low, high].
*/
int countPairs(vector<int>& nums, int low, int high) {
// Stores the final answer across all processed numbers.
int answer = 0;
// Process numbers one by one so the trie always contains only previous elements.
for (int num : nums) {
// Count pairs with XOR in [low, high] by subtracting two strict-limit counts.
answer += countLessThan(num, high + 1) - countLessThan(num, low);
// Insert after querying so the current number is not paired with itself.
insert(num);
}
return answer;
}
};
// Driver code starts
int main() {
vector<int> nums = {1, 4, 2, 7};
int low = 2;
int high = 6;
Solution obj;
cout << obj.countPairs(nums, low, high) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N * B), where B is the number of bits. Here B = 16, so this is close to linear.

Space Complexity: O(N * B) in the worst case for the trie.

Interview follow-up Questions

Because the trie helper counts XOR values strictly smaller than a limit. So values up to high are counted by using limit high + 1.

TrieMathsData Structures

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.5k
Binary Search TreeStackData StructuresRecursion

Range Sum of BST

cpp // C++ program to implement Range Sum of BST #include using namespace std; /* Definition for a binary tree node */ struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) :...

87.7k
TrieArraysData StructuresHashingStringSorting

Design Add and Search Words Data Structure

Design a data structure that supports adding words and searching words later. The search word may contain lowercase letters and the dot character . . The dot . can match any one lowercase English l...

50.7k
Comments0