3729. Count Distinct Subarrays Divisible by K in Sorted Array Hard

1/**
2 * [3729] Count Distinct Subarrays Divisible by K in Sorted Array
3 *
4 * You are given an integer array nums sorted in non-descending order and a positive integer k.
5 * A <span data-keyword="subarray-nonempty">subarray</span> of nums is good if the sum of its elements is divisible by k.
6 * Return an integer denoting the number of distinct good subarrays of nums.
7 * Subarrays are distinct if their sequences of values are. For example, there are 3 distinct subarrays in [1, 1, 1], namely [1], [1, 1], and [1, 1, 1].
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [1,2,3], k = 3</span>
12 * Output: <span class="example-io">3</span>
13 * Explanation:
14 * The good subarrays are [1, 2], [3], and [1, 2, 3]. For example, [1, 2, 3] is good because the sum of its elements is 1 + 2 + 3 = 6, and 6 % k = 6 % 3 = 0.
15 * </div>
16 * <strong class="example">Example 2:
17 * <div class="example-block">
18 * Input: <span class="example-io">nums = [2,2,2,2,2,2], k = 6</span>
19 * Output: <span class="example-io">2</span>
20 * Explanation:
21 * The good subarrays are [2, 2, 2] and [2, 2, 2, 2, 2, 2]. For example, [2, 2, 2] is good because the sum of its elements is 2 + 2 + 2 = 6, and 6 % k = 6 % 6 = 0.
22 * Note that [2, 2, 2] is counted only once.
23 * </div>
24 *  
25 * Constraints:
26 * 
27 * 	1 <= nums.length <= 10^5
28 * 	1 <= nums[i] <= 10^9
29 * 	nums is sorted in non-descending order.
30 * 	1 <= k <= 10^9
31 * 
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/count-distinct-subarrays-divisible-by-k-in-sorted-array/
36// discuss: https://leetcode.com/problems/count-distinct-subarrays-divisible-by-k-in-sorted-array/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn num_good_subarrays(nums: Vec<i32>, k: i32) -> i64 {
42        
43    }
44}
45
46// submission codes end
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn test_3729() {
54    }
55}
56