diff options
author | Jack Sangdahl <[email protected]> | 2024-09-17 00:13:00 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-17 00:13:00 -0600 |
commit | c37446194e37078adf18f5b50858352e1a745004 (patch) | |
tree | acc01f8c0cbdd73561e98f0f2252d35116db2b07 /count_pairs_xor_range.py | |
parent | 0d32ec5592060820b318ffc0ce85d9c99cf57159 (diff) | |
download | leetcode-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.py | 35 |
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)) |