aboutsummaryrefslogtreecommitdiff
path: root/count_interesting_subarr.c
blob: 0a379d5a39b0531c6d8948512428420c1246a42b (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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 2845. Count of Interesting Subarrays
#include "leetcode.h"

/*
 * you are given a 0-indexed integer array 'nums', an integer 'modulo', and an
 * integer 'k'. your task is to find the count of the subarrays that are
 * interesting. a subarray 'nums[l..r]' is interesting if the following
 * condition holds: let 'cnt' be the number of indices 'i' in the range '[l, r]'
 * such that 'nums[i] % modulo == k'. then 'cnt % modulo == k'. return an
 * integer denoting the count of interesting subarrays.
 */

struct pair {
  int key;
  int val;
};

struct hash {
  struct pair *pairs;
  int size;
  int max;
};

struct hash *hash_init(int size) {
  struct hash *new = (struct hash *)malloc(sizeof(struct hash));
  new->pairs = (struct pair *)malloc(size * sizeof(struct pair));
  new->size = 0;
  new->max = size;
  return new;
}

int get(struct hash *obj, int key) {
  for (int i = 0; i < obj->size; i++)
    if (obj->pairs[i].key == key)
      return obj->pairs[i].val;
  return 0;
}

void put(struct hash *obj, int key, int val) {
  for (int i = 0; i < obj->size; i++)
    if (obj->pairs[i].key == key) {
      obj->pairs[i].val = val;
      return;
    }
  if (obj->size == obj->max) {
    obj->max *= 2;
    obj->pairs =
        (struct pair *)realloc(obj->pairs, obj->max * sizeof(struct pair));
  }
  obj->pairs[obj->size].key = key;
  obj->pairs[obj->size].val = val;
  obj->size++;
}

void hash_free(struct hash *obj) {
  free(obj->pairs);
  free(obj);
}

long long countInterestingSubarrays(int *nums, int numsSize, int modulo,
                                    int k) {
  int cnt = 0;
  struct hash *map = hash_init(numsSize);
  put(map, 0, 1);
  long long ans = 0;
  for (int i = 0; i < numsSize; i++) {
    cnt += (nums[i] % modulo == k);
    int k1 = cnt % modulo;
    int k2 = (k1 - k + modulo) % modulo;
    ans += get(map, k2);
    put(map, k1, get(map, k1) + 1);
  }
  hash_free(map);
  return ans;
}

int main() {
  int n1[] = {3, 2, 4}, n2[] = {3, 1, 9, 6};
  printf("%lld\n",
         countInterestingSubarrays(n1, ARRAY_SIZE(n1), 2, 1)); // expect: 3
  printf("%lld\n",
         countInterestingSubarrays(n2, ARRAY_SIZE(n2), 3, 0)); // expect: 2
}