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
iwherenums1[i] != nums2[i].
A subarray is defined as a non-empty contiguous sequence of elements in an array.
Follow up: Can you solve this problem in O(n^2) time complexity?
Example 1
Input
nums = [2,3,3,2,2], k = 2, p = 2Output
11The 11 listed distinct subarrays have at most 2 elements divisible by 2, while
[2,3,3,2,2] has 3 such elements and is not counted.Example 2
Input
nums = [1,2,3,4], k = 4, p = 1Output
10Every subarray has at most 4 elements divisible by 1, and all 10 subarrays of
nums are distinct.Constraints
- 1 <= nums.length <= 200
- 1 <= nums[i], p <= 200
- 1 <= k <= nums.length