Skip to content

Commit 5db5219

Browse files
haoelhaoel
committed
New Problem Solution -"Count Pairs With XOR in a Range"
1 parent dbd221d commit 5db5219

File tree

2 files changed

+186
-0
lines changed

2 files changed

+186
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ LeetCode
99

1010
| # | Title | Solution | Difficulty |
1111
|---| ----- | -------- | ---------- |
12+
|1803|[Count Pairs With XOR in a Range](https://leetcode.com/problems/count-pairs-with-xor-in-a-range/) | [C++](./algorithms/cpp/countPairsWithXorInARange/CountPairsWithXorInARange.cpp)|Hard|
1213
|1802|[Maximum Value at a Given Index in a Bounded Array](https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/) | [C++](./algorithms/cpp/maximumValueAtAGivenIndexInABoundedArray/MaximumValueAtAGivenIndexInABoundedArray.cpp)|Medium|
1314
|1801|[Number of Orders in the Backlog](https://leetcode.com/problems/number-of-orders-in-the-backlog/) | [C++](./algorithms/cpp/numberOfOrdersInTheBacklog/NumberOfOrdersInTheBacklog.cpp)|Medium|
1415
|1800|[Maximum Ascending Subarray Sum](https://leetcode.com/problems/maximum-ascending-subarray-sum/) | [C++](./algorithms/cpp/maximumAscendingSubarraySum/MaximumAscendingSubarraySum.cpp)|Easy|

‎algorithms/cpp/countPairsWithXorInARange/CountPairsWithXorInARange.cpp

Lines changed: 185 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,185 @@
1+
// Source : https://leetcode.com/problems/count-pairs-with-xor-in-a-range/
2+
// Author : Hao Chen
3+
// Date : 2021-03-21
4+
5+
/*****************************************************************************************************
6+
*
7+
* Given a (0-indexed) integer array nums and two integers low and high, return the number of nice
8+
* pairs.
9+
*
10+
* A nice pair is a pair (i, j) where 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <=
11+
* high.
12+
*
13+
* Example 1:
14+
*
15+
* Input: nums = [1,4,2,7], low = 2, high = 6
16+
* Output: 6
17+
* Explanation: All nice pairs (i, j) are as follows:
18+
* - (0, 1): nums[0] XOR nums[1] = 5
19+
* - (0, 2): nums[0] XOR nums[2] = 3
20+
* - (0, 3): nums[0] XOR nums[3] = 6
21+
* - (1, 2): nums[1] XOR nums[2] = 6
22+
* - (1, 3): nums[1] XOR nums[3] = 3
23+
* - (2, 3): nums[2] XOR nums[3] = 5
24+
*
25+
* Example 2:
26+
*
27+
* Input: nums = [9,8,4,2,1], low = 5, high = 14
28+
* Output: 8
29+
* Explanation: All nice pairs (i, j) are as follows:
30+
* - (0, 2): nums[0] XOR nums[2] = 13
31+
* - (0, 3): nums[0] XOR nums[3] = 11
32+
* - (0, 4): nums[0] XOR nums[4] = 8
33+
* - (1, 2): nums[1] XOR nums[2] = 12
34+
* - (1, 3): nums[1] XOR nums[3] = 10
35+
* - (1, 4): nums[1] XOR nums[4] = 9
36+
* - (2, 3): nums[2] XOR nums[3] = 6
37+
* - (2, 4): nums[2] XOR nums[4] = 5
38+
*
39+
* Constraints:
40+
*
41+
* 1 <= nums.length <= 2 * 10^4
42+
* 1 <= nums[i] <= 2 * 10^4
43+
* 1 <= low <= high <= 2 * 10^4
44+
******************************************************************************************************/
45+
46+
/*
47+
The problem can be solved using Trie.
48+
49+
The idea is to iterate over the given array and for each array element,
50+
count the number of elements present in the Trie whose bitwise XOR with
51+
the current element is less than K and insert the binary representation
52+
of the current element into the Trie. Finally, print the count of pairs
53+
having bitwise XOR less than K. Follow the steps below to solve the problem:
54+
55+
- Create a Trie store the binary representation of each element of the given array.
56+
57+
- Traverse the given array, and count the number of elements present in the Trie
58+
whose bitwise XOR with the current element is less than K and insert the binary
59+
representation of the current element.
60+
61+
62+
Let's assume, we have an array [A, B, C, D, E], all of number are 5 bits.
63+
64+
Find a pair is (X, E) such that X ^ E < K. (Note: X could be A,B,C,D)
65+
66+
Now, let's say the binary of K = 11010. E = 01010.
67+
68+
from the left to right,
69+
70+
1) Step One - the 1st bit
71+
72+
K = 1 1 0 1 0
73+
E = 0 1 0 1 0
74+
^
75+
X = 0 x x x x -> all of number with `0` as the 1st bit need be count.
76+
77+
2) Step Two - the 2nd bit
78+
79+
K = 1 1 0 1 0
80+
E = 0 1 0 1 0
81+
^
82+
X = 1 1 x x x -> all of number with `1` as the 1st bit need be count.
83+
84+
3) Step Three - the 3rd bit
85+
86+
K = 1 1 0 1 0
87+
E = 0 1 0 1 0
88+
^
89+
X = 1 0 0 x x -> must be 0, and go to evaluate next bit
90+
91+
4) Step Four - the 4th bit
92+
93+
K = 1 1 0 1 0
94+
E = 0 1 0 1 0
95+
^
96+
X = 1 1 0 1 x -> all of number with `1` as the 1st bit need be count.
97+
98+
5) Step Five - the 5th bit
99+
100+
K = 1 1 0 1 0
101+
E = 0 1 0 1 0
102+
^
103+
X = 1 1 0 1 0 -> must be 0, and go to evaluate next bit
104+
105+
So, all of number will be sum of (step one, two, four)
106+
107+
*/
108+
109+
const int LEVEL = 16; // 1 <= nums[i] <= 20000
110+
111+
struct TrieNode {
112+
TrieNode *child[2]; // Stores binary represention of numbers
113+
int cnt; // Stores count of elements present in a node
114+
TrieNode() {
115+
child[0] = child[1] = NULL;
116+
cnt = 0;
117+
}
118+
};
119+
120+
121+
// Function to insert a number into Trie
122+
void insertTrie(TrieNode *root, int n) {
123+
// Traverse binary representation of X
124+
for (int i = LEVEL; i >= 0; i--) {
125+
// Stores ith bit of N
126+
bool x = (n) & (1 << i);
127+
// Check if an element already present in Trie having ith bit x
128+
if(!root->child[x]) {
129+
// Create a new node of Trie.
130+
root->child[x] = new TrieNode();
131+
}
132+
// Update count of elements whose ith bit is x
133+
root->child[x]->cnt += 1;
134+
135+
//Go to next level
136+
root = root->child[x];
137+
}
138+
}
139+
140+
141+
class Solution {
142+
private:
143+
// Count elements in Trie whose XOR with N less than K
144+
int countSmallerPairs(TrieNode * root, int N, int K) {
145+
// Stores count of elements whose XOR with N less than K
146+
int cntPairs = 0;
147+
// Traverse binary representation of N and K in Trie
148+
for (int i = LEVEL; i >= 0 && root; i--) {
149+
bool x = N & (1 << i); // Stores ith bit of N
150+
bool y = K & (1 << i); // Stores ith bit of K
151+
152+
// If the ith bit of K is 0
153+
if (y == 0 ) {
154+
// find the number which bit is same as N
155+
// so that they can be xored to ZERO
156+
root = root->child[x];
157+
continue;
158+
}
159+
// If the ith bit of K is 1
160+
// If an element already present in Trie having ith bit (x)
161+
if(root->child[x]) {
162+
// find the number which bit is same as N
163+
// so that they can be xored to ZERO. so it would be smaller than K
164+
cntPairs += root->child[x]->cnt;
165+
}
166+
//go to another way for next bit count
167+
root = root->child[1 - x];
168+
}
169+
return cntPairs;
170+
}
171+
public:
172+
int countPairs(vector<int>& nums, int low, int high) {
173+
174+
TrieNode* root = new TrieNode();
175+
176+
int cnt = 0;
177+
for (auto& num : nums) {
178+
cnt += countSmallerPairs(root, num, high + 1) - countSmallerPairs(root, num, low);
179+
insertTrie(root, num);
180+
}
181+
182+
183+
return cnt;
184+
}
185+
};

0 commit comments

Comments
 (0)