aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-07-05 14:29:01 -0600
committerJack Sangdahl <[email protected]>2024-07-05 14:29:01 -0600
commitfdc746d207c6b5ab558ac91622a93608cd0763c2 (patch)
treeeb14c02085522d5c6f7c367130aa2b5c2314a66c
parent08acd45da0244d0be7e59977e3427da7aefc8ac4 (diff)
downloadleetcode-fdc746d207c6b5ab558ac91622a93608cd0763c2.tar.gz
leetcode-fdc746d207c6b5ab558ac91622a93608cd0763c2.zip
2261. k divisible elements subarrays
-rw-r--r--k_div_element_subarr.c64
-rw-r--r--k_div_element_subarr.py37
2 files changed, 101 insertions, 0 deletions
diff --git a/k_div_element_subarr.c b/k_div_element_subarr.c
new file mode 100644
index 0000000..b9085ff
--- /dev/null
+++ b/k_div_element_subarr.c
@@ -0,0 +1,64 @@
+// 2261. K Divisible Elements Subarrays
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums' and two integers 'k' and 'p', return the number
+ * of distinct subarrays which have at most 'k' elements that are divisible by
+ * 'p'. two arrays 'nums1' and 'nums2' ae said to be distinct if they are of
+ * different lengths of there exists at least one index 'i' where 'nums1[i] !=
+ * nums2[i]'. a subarray is defined as a non empty contiguous sequence of
+ * elements in an array
+ */
+
+uint rs_hash(int *arr, int n) {
+ uint a = 6368973, b = 378551, res = 0;
+ for (int i = 0; i < n; i++) {
+ res = res * a + arr[i];
+ a *= b;
+ }
+ return res & 0x7FFFFFFF;
+}
+
+int countDistinct(int *nums, int numsSize, int k, int p) {
+ int n = numsSize, n2 = n * n, l = 0, r = 0, items = 0, ans = 0;
+ int **hash = (int **)calloc(n2, sizeof(int *));
+ int *cnt = (int *)calloc(201, sizeof(int));
+ for (r = 0; r < n; r++) {
+ cnt[nums[r]]++;
+ if (!(nums[r] % p))
+ items++;
+ while (items > k) {
+ cnt[nums[l]]--;
+ if (!(nums[l] % p))
+ items--;
+ l++;
+ }
+ for (int i = 0; i <= r; i++) {
+ uint val = rs_hash(&nums[i], r - i + 1);
+ int d = val;
+ while (1) {
+ if (!(hash[d % n2])) {
+ hash[d % n2] = malloc(2 * sizeof(int));
+ hash[d % n2][0] = val;
+ hash[d % n2][1] = 1;
+ ans++;
+ break;
+ } else {
+ if (hash[d % n2][0] == val) {
+ hash[d % n2][1]++;
+ break;
+ } else {
+ d++;
+ }
+ }
+ }
+ }
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {2, 3, 3, 2, 2}, n2[] = {1, 2, 3, 4};
+ printf("%d\n", countDistinct(n1, ARRAY_SIZE(n1), 2, 2)); // expect: 11
+ printf("%d\n", countDistinct(n2, ARRAY_SIZE(n2), 4, 1)); // expect: 10
+}
diff --git a/k_div_element_subarr.py b/k_div_element_subarr.py
new file mode 100644
index 0000000..7bf442b
--- /dev/null
+++ b/k_div_element_subarr.py
@@ -0,0 +1,37 @@
+# 2261. K Divisible Elements Subarrays
+
+"""
+given an integer array 'nums' and two integers 'k' and 'p', return the number
+of distinct subarrays which have at most 'k' elements that are divisible by
+'p'. two arrays 'nums1' and 'nums2' ae said to be distinct if they are of
+different lengths of there exists at least one index 'i' where 'nums1[i] !=
+nums2[i]'. a subarray is defined as a non empty contiguous sequence of
+elements in an array
+"""
+
+
+class Solution(object):
+ def countDistinct(self, nums, k, p):
+ """
+ :type nums: List[int]
+ :type k: int
+ :type p: int
+ :rtype: int
+ """
+ n, sub_arr = len(nums), set()
+ for i in range(n):
+ cnt, tmp = 0, ""
+ for j in range(i, n):
+ if nums[j] % p == 0:
+ cnt += 1
+ tmp += str(nums[i])
+ if cnt > k:
+ break
+ sub_arr.add(tmp)
+ return len(sub_arr)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countDistinct(nums=[2, 3, 3, 2, 2], k=2, p=2))
+ print(obj.countDistinct(nums=[1, 2, 3, 4], k=4, p=1))