diff options
author | Jack Sangdahl <[email protected]> | 2024-09-30 20:47:43 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-30 20:47:43 -0600 |
commit | b8cd0d8b589f57f1c5604dcd3c0795992fbcdea0 (patch) | |
tree | 5fca2e1bb6d98a8d77f896a3d4fd6ad1eb4ed551 | |
parent | 3bef57ed2a7eac99f87a24fa02de6450c9fcff7b (diff) | |
download | leetcode-b8cd0d8b589f57f1c5604dcd3c0795992fbcdea0.tar.gz leetcode-b8cd0d8b589f57f1c5604dcd3c0795992fbcdea0.zip |
1497. check if array pairs are divisible by k
-rw-r--r-- | check_arr_div_k.c | 37 | ||||
-rw-r--r-- | check_arr_div_k.py | 40 |
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)) |