Count of Interesting Subarrays

Problem

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 cnt be the number of indices i in the range [l, r] such that nums[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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


Input: nums = [3,2,4], modulo = 2, k = 1
Output: 3
Explanation: In this example the interesting subarrays are: 
The subarray nums[0..0] which is [3]. 
- There is only one index, i = 0, in the range [0, 0] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 1 and cnt % modulo == k.  
The subarray nums[0..1] which is [3,2].
- There is only one index, i = 0, in the range [0, 1] that satisfies nums[i] % modulo == k.  
- Hence, cnt = 1 and cnt % modulo == k.
The subarray nums[0..2] which is [3,2,4]. 
- There is only one index, i = 0, in the range [0, 2] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 1 and cnt % modulo == k. 
It can be shown that there are no other interesting subarrays. So, the answer is 3.

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: nums = [3,1,9,6], modulo = 3, k = 0
Output: 2
Explanation: In this example the interesting subarrays are: 
The subarray nums[0..3] which is [3,1,9,6]. 
- There are three indices, i = 0, 2, 3, in the range [0, 3] that satisfy nums[i] % modulo == k. 
- Hence, cnt = 3 and cnt % modulo == k. 
The subarray nums[1..1] which is [1]. 
- There is no index, i, in the range [1, 1] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 0 and cnt % modulo == k. 
It can be shown that there are no other interesting subarrays. So, the answer is 2.

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= modulo <= 109
0 <= k < modulo

Solution

Method 1 - Using Prefix Sums

To solve this problem, the goal is to efficiently determine the count of “interesting” subarrays instead of naively calculating for all possible subarrays. Using mathematical insights regarding modulo operations and prefix sums can significantly optimise the solution.

A subarray is interesting if the number of indices i within the subarray where nums[i] % modulo == k satisfies:

1

cnt % modulo == k

We’ll focus on efficiently counting these subarrays using prefix sums and hashmaps.

So, we can:

Convert each element nums[i] to 1 if nums[i] % modulo == k, otherwise 0.
Use a prefix sum array to calculate the count of such elements (as 1s) at each position.
The challenge now turns into finding valid subarrays such that: prefix[r] - prefix[l - 1] % modulo == k
Rearranging: prefix[r] % modulo == k + prefix[l - 1] % modulo

So, we

Use a hashmap to store the frequency of prefix sums modulo ( modulo ).
Iterate through the array and count valid subarrays using the insights above.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {

    public long countInterestingSubarrays(
        List<Integer> nums,
        int modulo,
        int k
    ) {
        long ans = 0; // To store the final count of interesting subarrays
        int prefix = 0; // Prefix sum modulo counter
        HashMap<Integer, Integer> freq = new HashMap<>();
        freq.put(0, 1); // Initial condition: one subarray starting at index 0

        for (int num : nums) {
            // Update prefix when nums[i] % modulo == k
            if (num % modulo == k) {
                prefix++;
            }
            // Compute current prefix modulo
            int prefixMod = prefix % modulo;
            // Compute the target (satisfying condition cnt % modulo == k)
            int target = (prefixMod - k + modulo) % modulo;

            // Add the count of this target prefix to the result
            ans += freq.getOrDefault(target, 0);

            // Update the frequency map with the current prefix modulo
            freq.put(prefixMod, freq.getOrDefault(prefixMod, 0) + 1);
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        ans = 0
        prefix = 0
        freq = {0: 1}
        
        for num in nums:
            # Update prefix sum modulo `modulo`
            if num % modulo == k:
                prefix += 1
            
            prefix_mod = prefix % modulo
            # Match condition:
            target = (prefix_mod - k) % modulo
            
            # Add the frequency of target to the count
            ans += freq.get(target, 0)
            
            # Update frequency map
            freq[prefix_mod] = freq.get(prefix_mod, 0) + 1
        
        return ans

Complexity

⏰ Time complexity: O(n) because we compute prefix sums and search/update the hashmap in one pass.
🧺 Space complexity: O(modulo) due to storage of prefix sums modulo values in the hashmap.

Problem#

Examples#

Solution#

Method 1 - Using Prefix Sums#

Code#

Complexity#