Introduction
The problem is to find the number of pairs (i, j) in an array such that the bitwise XOR of the pair is less than a given integer k.
For example, given the array [1, 2, 3, 5] and k = 5, the valid pairs are:
1 ^ 2 = 3
1 ^ 3 = 2
1 ^ 5 = 4
2 ^ 3 = 1
Thus, the output is 4.
Understanding XOR and Pairs
The bitwise XOR operator (^) compares two numbers bit by bit. The XOR of two numbers is less than k if their binary representation results in a number smaller than the binary representation of k.
A brute-force solution would check all possible pairs:
for i = 0 to n-1:
for j = i+1 to n-1:
if (arr[i] ^ arr[j]) < k:
count++
This works in O(n²) time, but for large arrays (n up to 5 * 10⁴), this is too slow.
Optimized Approach Using Trie
We can optimize using a Trie (prefix tree) built for binary representations of numbers.
Key Idea
Insert numbers into the Trie as we iterate through the array.
For each number, count how many previously inserted numbers produce XOR < k.
Each node in the Trie represents a single bit (0 or 1).
At each bit level, we decide whether we can choose 0 or 1 based on the corresponding bit of k.
How Counting Works
Consider a number num and k in binary.
We traverse the Trie from the most significant bit (MSB) to the least significant bit (LSB).
At each bit:
If the bit in k is 1, we can take all numbers with the same bit as num in this position (because XOR with 0 or 1 may still be less than k).
If the bit in k is 0, we can only go to the branch that has the same bit as num.
This ensures we count only those numbers whose XOR with num is less than k.
Java Solution
class Solution {
static class TrieNode {
TrieNode[] child = new TrieNode[2];
int count = 0; // Count of numbers passing through this node
}
public int cntPairs(int[] arr, int k) {
TrieNode root = new TrieNode();
int count = 0;
for (int num : arr) {
count += countLessXOR(root, num, k, 15); // max 15 bits because arr[i] <= 5*10^4
insert(root, num, 15);
}
return count;
}
private void insert(TrieNode root, int num, int bit) {
TrieNode node = root;
for (int i = bit; i >= 0; i--) {
int b = (num >> i) & 1;
if (node.child[b] == null) {
node.child[b] = new TrieNode();
}
node = node.child[b];
node.count++;
}
}
private int countLessXOR(TrieNode root, int num, int k, int bit) {
TrieNode node = root;
int count = 0;
for (int i = bit; i >= 0 && node != null; i--) {
int bNum = (num >> i) & 1;
int bK = (k >> i) & 1;
if (bK == 1) {
// Add count of numbers with same bit as bNum
if (node.child[bNum] != null) {
count += node.child[bNum].count;
}
node = node.child[1 - bNum]; // Move to opposite branch
} else {
node = node.child[bNum]; // Only same bit branch allowed
}
}
return count;
}
}
Example Run
Input
arr = [1, 2, 3, 5], k = 5
Step-by-Step
Final answer = 4
Complexity Analysis
Time Complexity
O(n * log(max(arr[i])))
Since numbers are bounded by 5 * 10⁴ and:
log2(5 * 10^4) ≈ 16
the complexity is effectively O(n).
Space Complexity
O(n * log(max(arr[i])))
This space is used for storing Trie nodes.
Key Insight
Trie helps efficiently count numbers whose XOR with a given number is less than k. Instead of checking all possible pairs, we navigate the binary bits of the numbers and k to prune impossible options. This reduces the complexity dramatically from O(n²) to nearly O(n) and makes the solution practical for large input sizes.
Summary
To count pairs whose XOR is less than a given value k, a brute-force approach becomes inefficient for large arrays because it requires checking every pair. A Trie-based solution stores binary representations of previously seen numbers and efficiently counts valid XOR combinations bit by bit. By leveraging the binary properties of XOR and the structure of a Trie, the algorithm reduces the time complexity from O(n²) to approximately O(n), making it suitable for arrays containing tens of thousands of elements.