2261. K Divisible Elements Subarrays Medium

1use std::collections::HashSet;
2
3/**
4 * [2261] K Divisible Elements Subarrays
5 *
6 * Given an integer array nums and two integers k and p, return the number of distinct subarrays which have at most k elements divisible by p.
7 * Two arrays nums1 and nums2 are said to be distinct if:
8 * 
9 * They are of different lengths, or
10 * There exists at least one index i where nums1[i] != nums2[i].
11 * 
12 * A subarray is defined as a non-empty contiguous sequence of elements in an array.
13 *  
14 * Example 1:
15 * 
16 * Input: nums = [<u>2</u>,3,3,<u>2</u>,<u>2</u>], k = 2, p = 2
17 * Output: 11
18 * Explanation:
19 * The elements at indices 0, 3, and 4 are divisible by p = 2.
20 * The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are:
21 * [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].
22 * Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once.
23 * The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.
24 * 
25 * Example 2:
26 * 
27 * Input: nums = [1,2,3,4], k = 4, p = 1
28 * Output: 10
29 * Explanation:
30 * All element of nums are divisible by p = 1.
31 * Also, every subarray of nums will have at most 4 elements that are divisible by 1.
32 * Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.
33 * 
34 *  
35 * Constraints:
36 * 
37 * 1 <= nums.length <= 200
38 * 1 <= nums[i], p <= 200
39 * 1 <= k <= nums.length
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/k-divisible-elements-subarrays/
45// discuss: https://leetcode.com/problems/k-divisible-elements-subarrays/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn count_distinct(nums: Vec<i32>, k: i32, p: i32) -> i32 {
51        let mut map: HashSet<String> = HashSet::new();
52        
53        for i in 0..nums.len() {
54            let mut key = String::from("");
55            let mut count = 0;
56            for j in i..nums.len() {
57                if nums[j] % p == 0 {
58                    count += 1;
59                    if count > k {
60                        break;
61                    }
62                }
63                key.push(',');
64                key.push_str(&nums[j].to_string());
65                map.insert(key.clone());
66            }
67        }
68        map.len() as i32
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_2261_1() {
80        assert_eq!(Solution::count_distinct(vec!(1,2,3,4), 4, 1), 10);
81        assert_eq!(Solution::count_distinct(vec!(2,3,3,2,2), 2, 2), 11);
82    }
83}
84