aboutsummaryrefslogtreecommitdiff
path: root/subarr_sum_divisible_k.c
blob: 52014ab40a73d4b4bf6c70f5f7c9f0b64434ea27 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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
}