aboutsummaryrefslogtreecommitdiff
path: root/binary_subarr_sum.c
blob: c20bfdb311f170a0d5d8e719a45b2176eb980b81 (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
49
50
51
52
// 930. Binary Subarrays With Sum
#include "leetcode.h"

/*
 * given a binary array 'nums' and an integer 'goal', return the number o
 * non-empty subarrays with a sum 'goal'. a subarray is a contiguous part of the
 * array
 */

int numSubarraysWithSum(int *nums, int numsSize, int goal) {
  int n = numsSize, m = n + 1, sum = 0, rm, d, ans = 0;
  int **hash = calloc(m, sizeof(int *));
  hash[0] = malloc(2 * sizeof(int));
  hash[0][0] = 0;
  hash[0][1] = 1;
  for (int i = 0; i < n; i++) {
    sum += nums[i];
    rm = sum - goal;
    d = rm;
    while (1 && rm >= 0) {
      if (hash[d % n] == NULL)
        break;
      else if (hash[d % n][0] == rm) {
        ans += hash[d % n][1];
        break;
      } else {
        d++;
      }
    }
    d = sum;
    while (1) {
      if (hash[d % n] == NULL) {
        hash[d % n] = malloc(2 * sizeof(int));
        hash[d % n][0] = sum;
        hash[d % n][1] = 1;
        break;
      } else if (hash[d % n][0] == sum) {
        hash[d % n][1]++;
        break;
      } else {
        d++;
      }
    }
  }
  return ans;
}

int main() {
  int n1[] = {1, 0, 1, 0, 1}, n2[] = {0, 0, 0, 0, 0};
  printf("%d\n", numSubarraysWithSum(n1, ARRAY_SIZE(n1), 2)); // expect: 4
  printf("%d\n", numSubarraysWithSum(n2, ARRAY_SIZE(n2), 0)); // expect: 15
}