diff options
Diffstat (limited to 'subarr_sum_divisible_k.c')
-rw-r--r-- | subarr_sum_divisible_k.c | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/subarr_sum_divisible_k.c b/subarr_sum_divisible_k.c new file mode 100644 index 0000000..52014ab --- /dev/null +++ b/subarr_sum_divisible_k.c @@ -0,0 +1,48 @@ +// 974. Subarray Sums Divisible by K +#include <stdio.h> +#include <stdlib.h> + +/* + * given: integer array 'nums' and integer 'k' + * return: number of non-empty subarrays that + * have a sum divisible by 'k'. + * a subarray is a contiguous part of an array + */ + +int subarrayDivByK(int *nums, int numsSize, int k) { + if (numsSize == 0) + return 0; + else if (numsSize == 1) { + if (nums[0] % k == 0) + return 1; + else + return 0; + } + int ans = 0, *n, *hash; + n = malloc(numsSize * sizeof(int)); + hash = malloc(k * sizeof(int)); + for (int i = 0; i < k; i++) + hash[i] = 0; + n[0] = nums[0] % k; + if (n[0] < 0) + n[0] = n[0] + k; + hash[n[0]]++; + for (int i = 1; i < numsSize; i++) { + nums[i] = nums[i] + nums[i - 1]; + n[i] = nums[i] % k; + if (n[i] < 0) + n[i] = n[i] + k; + hash[n[i]]++; + } + ans += hash[0]; + for (int i = 0; i < k; i++) + if (hash[i] > 1) + ans += hash[i] * (hash[i] - 1) >> 1; + return ans; +} + +int main() { + int nums1[] = {4, 5, 0, -2, -3, 1}, nums2[] = {5}; + printf("%d\n", subarrayDivByK(nums1, 6, 5)); // expect: 7 + printf("%d\n", subarrayDivByK(nums2, 1, 9)); // expect: 0 +} |