Count subarrays whose number of elements matching a condition leaves a specified remainder modulo k.
Problem
You are given an integer array nums, an integer modulo, and an integer k.
A subarray is called interesting if the count of indices i in that subarray such that nums[i] % modulo == k is congruent to k modulo modulo.
Your task is to return the number of interesting subarrays.
Intuition behind the condition
For any subarray, let cnt be the number of elements inside it satisfying nums[i] % modulo == k. The subarray is interesting when:
cnt % modulo == k
Count all such subarrays.
Input Format
- An integer array
nums - An integer
modulo - An integer
k
Output Format
- Return the number of interesting subarrays.
Constraints
1 <= nums.length <= $10^{5}$1 <= modulo <= $10^{9}$0 <= k < modulo0 <= nums[i] <= $10^{9}$
Hints
- Convert each element into
1if it satisfies the conditionnums[i] % modulo == k, otherwise0. - Use prefix counts and observe what relationship must hold between two prefix values for a subarray to be interesting.
- A hash map can store how often each prefix remainder has appeared.
Input Format
nums: integer arraymodulo: positive integerk: integer with0 <= k < modulo
Output Format
- Return an integer count of the subarrays that satisfy the condition.
Constraints
1 <= nums.length <= $10^{5}$1 <= modulo <= $10^{9}$0 <= k < modulo0 <= nums[i] <= $10^{9}$
Example 1
Input
nums = [3, 1, 9, 6], modulo = 3, k = 0
Output
6
Explanation
Every number is divisible by 3, so each element contributes to the count. A subarray is interesting when its length is divisible by 3. The interesting subarrays are [3,1,9], [1,9,6], [3,1,9,6] is not divisible by 3, and the single-element subarrays are not interesting. The total is 6.
Example 2
Input
nums = [2, 3, 5], modulo = 2, k = 1
Output
4
Explanation
Elements with nums[i] % 2 == 1 are 3 and 5. Count subarrays whose number of odd elements is odd. Those are [3], [5], [2,3], and [3,5].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.