From c37446194e37078adf18f5b50858352e1a745004 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Tue, 17 Sep 2024 00:13:00 -0600 Subject: 1803. count pairs with xor in a range --- count_pairs_xor_range.py | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 count_pairs_xor_range.py (limited to 'count_pairs_xor_range.py') 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)) -- cgit v1.2.3