K Divisible Elements Subarrays

// Accepted solution for LeetCode #2261: K Divisible Elements Subarrays
class Solution {
    public int countDistinct(int[] nums, int k, int p) {
        Set<Long> s = new HashSet<>();
        int n = nums.length;
        int base1 = 131, base2 = 13331;
        int mod1 = (int) 1e9 + 7, mod2 = (int) 1e9 + 9;
        for (int i = 0; i < n; ++i) {
            long h1 = 0, h2 = 0;
            int cnt = 0;
            for (int j = i; j < n; ++j) {
                cnt += nums[j] % p == 0 ? 1 : 0;
                if (cnt > k) {
                    break;
                }
                h1 = (h1 * base1 + nums[j]) % mod1;
                h2 = (h2 * base2 + nums[j]) % mod2;
                s.add(h1 << 32 | h2);
            }
        }
        return s.size();
    }
}

// Accepted solution for LeetCode #2261: K Divisible Elements Subarrays
func countDistinct(nums []int, k int, p int) int {
	s := map[int]bool{}
	base1, base2 := 131, 13331
	mod1, mod2 := 1000000007, 1000000009
	for i := range nums {
		h1, h2, cnt := 0, 0, 0
		for j := i; j < len(nums); j++ {
			if nums[j]%p == 0 {
				cnt++
				if cnt > k {
					break
				}
			}
			h1 = (h1*base1 + nums[j]) % mod1
			h2 = (h2*base2 + nums[j]) % mod2
			s[h1<<32|h2] = true
		}
	}
	return len(s)
}

# Accepted solution for LeetCode #2261: K Divisible Elements Subarrays
class Solution:
    def countDistinct(self, nums: List[int], k: int, p: int) -> int:
        s = set()
        n = len(nums)
        base1, base2 = 131, 13331
        mod1, mod2 = 10**9 + 7, 10**9 + 9
        for i in range(n):
            h1 = h2 = cnt = 0
            for j in range(i, n):
                cnt += nums[j] % p == 0
                if cnt > k:
                    break
                h1 = (h1 * base1 + nums[j]) % mod1
                h2 = (h2 * base2 + nums[j]) % mod2
                s.add(h1 << 32 | h2)
        return len(s)

// Accepted solution for LeetCode #2261: K Divisible Elements Subarrays
/**
 * [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 are said to be distinct if:
 *
 * 	They are of different lengths, or
 * 	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.
 *  
 * Example 1:
 *
 * Input: nums = [<u>2</u>,3,3,<u>2</u>,<u>2</u>], k = 2, p = 2
 * Output: 11
 * Explanation:
 * The elements at indices 0, 3, and 4 are divisible by p = 2.
 * The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are:
 * [2], [2,3], [2,3,3], [2,3,3,2], [3], [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], and [2,2].
 * Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once.
 * The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.
 *
 * Example 2:
 *
 * Input: nums = [1,2,3,4], k = 4, p = 1
 * Output: 10
 * Explanation:
 * All element of nums are divisible by p = 1.
 * Also, every subarray of nums will have at most 4 elements that are divisible by 1.
 * Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.
 *
 *  
 * Constraints:
 *
 * 	1 <= nums.length <= 200
 * 	1 <= nums[i], p <= 200
 * 	1 <= k <= nums.length
 *
 *  
 * Follow up:
 * Can you solve this problem in O(n^2) time complexity?
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/k-divisible-elements-subarrays/
// discuss: https://leetcode.com/problems/k-divisible-elements-subarrays/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn count_distinct(nums: Vec<i32>, k: i32, p: i32) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2261_example_1() {
        let nums = vec![2, 3, 3, 2, 2];
        let k = 2;
        let p = 2;

        let result = 11;

        assert_eq!(Solution::count_distinct(nums, k, p), result);
    }

    #[test]
    #[ignore]
    fn test_2261_example_2() {
        let nums = vec![1, 2, 3, 4];
        let k = 4;
        let p = 1;

        let result = 10;

        assert_eq!(Solution::count_distinct(nums, k, p), result);
    }
}

// Accepted solution for LeetCode #2261: K Divisible Elements Subarrays
function countDistinct(nums: number[], k: number, p: number): number {
    const s = new Set<bigint>();
    const [base1, base2] = [131, 13331];
    const [mod1, mod2] = [1000000007, 1000000009];
    for (let i = 0; i < nums.length; i++) {
        let [h1, h2, cnt] = [0, 0, 0];
        for (let j = i; j < nums.length; j++) {
            if (nums[j] % p === 0) {
                cnt++;
                if (cnt > k) {
                    break;
                }
            }
            h1 = (h1 * base1 + nums[j]) % mod1;
            h2 = (h2 * base2 + nums[j]) % mod2;
            s.add((BigInt(h1) << 32n) | BigInt(h2));
        }
    }
    return s.size;
}