Count of Interesting Subarrays
You are given a 0-indexed integer array nums, an integer modulo, and an integer k.
Your task is to find the count of subarrays that are interesting.
A subarray nums[l..r] is interesting if the following condition holds:
- Let
cntbe the number of indicesiin the range[l, r]such thatnums[i] % modulo == k. Then,cnt % modulo == k.
Return an integer denoting the count of interesting subarrays.
Note: A subarray is a contiguous non-empty sequence of elements within an array.
Example 1
Input
nums = [3,2,4], modulo = 2, k = 1Output
3The interesting subarrays are
nums[0..0], nums[0..1], and nums[0..2], so the answer is 3.Example 2
Input
nums = [3,1,9,6], modulo = 3, k = 0Output
2The interesting subarrays are
nums[0..3] and nums[1..1], so the answer is 2.Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= modulo <= 10^9
- 0 <= k < modulo