aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-24 19:56:03 -0600
committerJack Sangdahl <[email protected]>2025-04-24 19:56:03 -0600
commitcb5eca9739f1acc70755952819206e40cd76a078 (patch)
tree7612019b953d7712a342c0928e49d9cb3f57f5e4
parent5bacbd9adc737abe8757fce08c4174696719cc26 (diff)
downloadleetcode-cb5eca9739f1acc70755952819206e40cd76a078.tar.gz
leetcode-cb5eca9739f1acc70755952819206e40cd76a078.zip
2845. count of interesting subarrays
-rw-r--r--count_interesting_subarr.c83
-rw-r--r--count_interesting_subarr.py34
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))