diff options
author | Jack Sangdahl <[email protected]> | 2025-04-16 18:23:44 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-16 18:23:44 -0600 |
commit | 614e2a72867982fe67dd0c6351ae647fbb1b7866 (patch) | |
tree | 169e3a70ce6bb9fdc0923d9184832776db3fef8a /count_equal_div_pair_arr.py | |
parent | c31e6747422d487d3d3c6a3b5886f88da7c2e5eb (diff) | |
download | leetcode-614e2a72867982fe67dd0c6351ae647fbb1b7866.tar.gz leetcode-614e2a72867982fe67dd0c6351ae647fbb1b7866.zip |
2176. count equal and divisible pairs in an array
Diffstat (limited to 'count_equal_div_pair_arr.py')
-rw-r--r-- | count_equal_div_pair_arr.py | 37 |
1 files changed, 37 insertions, 0 deletions
diff --git a/count_equal_div_pair_arr.py b/count_equal_div_pair_arr.py new file mode 100644 index 0000000..84d4a55 --- /dev/null +++ b/count_equal_div_pair_arr.py @@ -0,0 +1,37 @@ +# 2176. Count Equal and Divisible Pairs in an Array +import collections +from math import gcd + +""" +given a 0-indexed integer array 'nums' of length 'n' and an integer 'k', +return the number of pairs '(i, j)' where '0 <= i < j < n' such that 'nums[i] +== nums[j]' and '(i * j)' is divisble by 'k'. +""" + + +class Solution(object): + def countPairs(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + ids = collections.defaultdict(list) + for i, j in enumerate(nums): + ids[j].append(i) + ans = 0 + for i in ids.values(): + gcds = collections.Counter() + for j in i: + curr_i = gcd(j, k) + ans += sum( + cnt for curr_j, cnt in gcds.items() if curr_i * curr_j % k == 0 + ) + gcds[curr_i] += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countPairs(nums=[3, 1, 2, 2, 2, 1, 3], k=2)) + print(obj.countPairs(nums=[1, 2, 3, 4], k=1)) |