aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_equal_div_pair_arr.c23
-rw-r--r--count_equal_div_pair_arr.py37
2 files changed, 60 insertions, 0 deletions
diff --git a/count_equal_div_pair_arr.c b/count_equal_div_pair_arr.c
new file mode 100644
index 0000000..d6aeb12
--- /dev/null
+++ b/count_equal_div_pair_arr.c
@@ -0,0 +1,23 @@
+// 2176. Count Equal and Divisible Pairs in an Array
+#include "leetcode.h"
+
+/*
+ * 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'.
+ */
+
+int countPairs(int *nums, int numsSize, int k) {
+ int cnt = 0;
+ for (int i = 0; i < numsSize; i++)
+ for (int j = i + 1; j < numsSize; j++)
+ if (nums[i] == nums[j] && !((i * j) % k))
+ cnt++;
+ return cnt;
+}
+
+int main() {
+ int n1[] = {3, 1, 2, 2, 2, 1, 3}, n2[] = {1, 2, 3, 4};
+ printf("%d\n", countPairs(n1, ARRAY_SIZE(n1), 2)); // expect: 4
+ printf("%d\n", countPairs(n2, ARRAY_SIZE(n2), 1)); // expect: 0
+}
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))