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
}
|