aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-30 20:47:43 -0600
committerJack Sangdahl <[email protected]>2024-09-30 20:47:43 -0600
commitb8cd0d8b589f57f1c5604dcd3c0795992fbcdea0 (patch)
tree5fca2e1bb6d98a8d77f896a3d4fd6ad1eb4ed551
parent3bef57ed2a7eac99f87a24fa02de6450c9fcff7b (diff)
downloadleetcode-b8cd0d8b589f57f1c5604dcd3c0795992fbcdea0.tar.gz
leetcode-b8cd0d8b589f57f1c5604dcd3c0795992fbcdea0.zip
1497. check if array pairs are divisible by k
-rw-r--r--check_arr_div_k.c37
-rw-r--r--check_arr_div_k.py40
2 files changed, 77 insertions, 0 deletions
diff --git a/check_arr_div_k.c b/check_arr_div_k.c
new file mode 100644
index 0000000..83c460a
--- /dev/null
+++ b/check_arr_div_k.c
@@ -0,0 +1,37 @@
+// 1497. Check If Array Pairs Are Divisible by k
+#include "leetcode.h"
+
+/*
+ * given an array of integers 'arr' of even length 'n' and an integer 'k'. we
+ * want to divide the array into exactly 'n / 2' pairs such that the sum of each
+ * pair is divisible by 'k'. return 'true' if you can find a way to to that or
+ * 'false' otherwise.
+ */
+
+bool canArrange(int *arr, int arrSize, int k) {
+ int *freq = (int *)calloc(k, sizeof(int));
+ for (int i = 0; i < arrSize; i++) {
+ int rem = ((arr[i] % k) + k) % k;
+ freq[rem]++;
+ }
+ if (freq[0] % 2)
+ return false;
+ if (!(k % 2))
+ if (freq[k / 2] % 2) {
+ free(freq);
+ return false;
+ }
+ for (int r = 1; r <= k / 2; r++)
+ if (r != k - r)
+ if (freq[r] != freq[k - r])
+ return false;
+ return true;
+}
+
+int main() {
+ int a1[] = {1, 2, 3, 4, 5, 10, 6, 7, 8, 9}, a2[] = {1, 2, 3, 4, 5, 6},
+ a3[] = {1, 2, 3, 4, 5, 6};
+ printf("%d\n", canArrange(a1, ARRAY_SIZE(a1), 5)); // expect: 1
+ printf("%d\n", canArrange(a2, ARRAY_SIZE(a2), 7)); // expect: 1
+ printf("%d\n", canArrange(a3, ARRAY_SIZE(a3), 10)); // expect: 0
+}
diff --git a/check_arr_div_k.py b/check_arr_div_k.py
new file mode 100644
index 0000000..26febb4
--- /dev/null
+++ b/check_arr_div_k.py
@@ -0,0 +1,40 @@
+# 1497. Check If Array Pairs Are Divisible by k
+
+"""
+given an array of integers 'arr' of even length 'n' and an integer 'k'. we
+want to divide the array into exactly 'n / 2' pairs such that the sum of each
+pair is divisible by 'k'. return 'true' if you can find a way to to that or
+'false' otherwise.
+"""
+
+
+class Solution(object):
+ def canArrange(self, arr, k):
+ """
+ :type arr: List[int]
+ :type k: int
+ :rtype: bool
+ """
+ cnt = [0] * k
+ for i in arr:
+ cnt[i % k] += 1
+ i, j = 1, k - 1
+ pairs = 0
+ while i < j:
+ if cnt[i] != cnt[j]:
+ return False
+ pairs += cnt[i]
+ i += 1
+ j -= 1
+ if pairs > 0 and i == j:
+ pairs += cnt[i] / 2
+ pairs += cnt[0] / 2
+ n = len(arr)
+ return pairs == n // 2
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.canArrange(arr=[1, 2, 3, 4, 5, 10, 6, 7, 8, 9], k=5))
+ print(obj.canArrange(arr=[1, 2, 3, 4, 5, 6], k=7))
+ print(obj.canArrange(arr=[1, 2, 3, 4, 5, 6], k=10))