aboutsummaryrefslogtreecommitdiff
path: root/count_pairs_xor_range.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-17 00:13:00 -0600
committerJack Sangdahl <[email protected]>2024-09-17 00:13:00 -0600
commitc37446194e37078adf18f5b50858352e1a745004 (patch)
treeacc01f8c0cbdd73561e98f0f2252d35116db2b07 /count_pairs_xor_range.py
parent0d32ec5592060820b318ffc0ce85d9c99cf57159 (diff)
downloadleetcode-c37446194e37078adf18f5b50858352e1a745004.tar.gz
leetcode-c37446194e37078adf18f5b50858352e1a745004.zip
1803. count pairs with xor in a range
Diffstat (limited to 'count_pairs_xor_range.py')
-rw-r--r--count_pairs_xor_range.py35
1 files changed, 35 insertions, 0 deletions
diff --git a/count_pairs_xor_range.py b/count_pairs_xor_range.py
new file mode 100644
index 0000000..01f2b84
--- /dev/null
+++ b/count_pairs_xor_range.py
@@ -0,0 +1,35 @@
+# 1803. Count Pairs With XOR in a Range
+from collections import Counter
+
+"""
+given a 0-indexed integer array 'numss' and two integers 'low' and 'high',
+return the numsber of nice pairs. a nice pair is a pair '(i, j)' where '0 <=
+i < j < numss.len' and 'low <= (numss[i] ^ numss[j]) <= high'.
+"""
+
+
+class Solution(object):
+ def countPairs(self, nums, low, high):
+ """
+ :type nums: List[int]
+ :type low: int
+ :type high: int
+ :rtype: int
+ """
+
+ def check(nums, x):
+ cnt, res = Counter(nums), 0
+ while x:
+ if x & 1:
+ res += sum(cnt[i] * cnt[(x - 1) ^ i] for i in cnt)
+ cnt = Counter({i >> 1: cnt[i] + cnt[i + 1] for i in cnt})
+ x >>= 1
+ return res // 2
+
+ return check(nums, high + 1) - check(nums, low)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countPairs(nums=[1, 4, 2, 7], low=2, high=6))
+ print(obj.countPairs(nums=[9, 8, 4, 2, 1], low=5, high=14))