diff options
author | Jack Sangdahl <[email protected]> | 2025-04-24 19:56:03 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-24 19:56:03 -0600 |
commit | cb5eca9739f1acc70755952819206e40cd76a078 (patch) | |
tree | 7612019b953d7712a342c0928e49d9cb3f57f5e4 | |
parent | 5bacbd9adc737abe8757fce08c4174696719cc26 (diff) | |
download | leetcode-cb5eca9739f1acc70755952819206e40cd76a078.tar.gz leetcode-cb5eca9739f1acc70755952819206e40cd76a078.zip |
2845. count of interesting subarrays
-rw-r--r-- | count_interesting_subarr.c | 83 | ||||
-rw-r--r-- | count_interesting_subarr.py | 34 |
2 files changed, 117 insertions, 0 deletions
diff --git a/count_interesting_subarr.c b/count_interesting_subarr.c new file mode 100644 index 0000000..0a379d5 --- /dev/null +++ b/count_interesting_subarr.c @@ -0,0 +1,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 +} diff --git a/count_interesting_subarr.py b/count_interesting_subarr.py new file mode 100644 index 0000000..9e76d99 --- /dev/null +++ b/count_interesting_subarr.py @@ -0,0 +1,34 @@ +# 2845. Count of Interesting Subarrays +from collections import Counter + +""" +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. +""" + + +class Solution(object): + def countInterestingSubarrays(self, nums, modulo, k): + """ + :type nums: List[int] + :type modulo: int + :type k: int + :rtype: int + """ + ans, cnt = 0, 0 + m = Counter({0: 1}) + for i in nums: + cnt = (cnt + (1 if i % modulo == k else 0)) % modulo + ans += m[(cnt - k) % modulo] + m[cnt] += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countInterestingSubarrays(nums=[3, 2, 4], modulo=2, k=1)) + print(obj.countInterestingSubarrays(nums=[3, 1, 9, 6], modulo=3, k=0)) |