diff options
author | Jack Sangdahl <[email protected]> | 2024-07-05 14:29:01 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-07-05 14:29:01 -0600 |
commit | fdc746d207c6b5ab558ac91622a93608cd0763c2 (patch) | |
tree | eb14c02085522d5c6f7c367130aa2b5c2314a66c | |
parent | 08acd45da0244d0be7e59977e3427da7aefc8ac4 (diff) | |
download | leetcode-fdc746d207c6b5ab558ac91622a93608cd0763c2.tar.gz leetcode-fdc746d207c6b5ab558ac91622a93608cd0763c2.zip |
2261. k divisible elements subarrays
-rw-r--r-- | k_div_element_subarr.c | 64 | ||||
-rw-r--r-- | k_div_element_subarr.py | 37 |
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)) |