2845. 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 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.

Example 1:

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:

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.

APPROACH

1

[3,2,4] - modulo = 2, k = 1, Ans: 3

Ans arrays: [3] and [3,2] and [3,2,4]

• First let us try to store what all individual elements that divide by modulo and give k
• [1 0 0 ] // 1 indicates interesting 0 indicates not interesting
• Now take the prefix sum - [1 1 1]
• Take modulo of each element in prefix sum and check k - if you get k - you can count 1 to ans

2

[3,1,9,6] - modulo = 3, k = 0, Ans: 2

Ans arrays: [3,1,9,6] and [1]

• First let us try to store what all individual elements that divide by modulo and give k
• [3,1,9,6] - [1 0 1 1]
• Now take the prefix sum - [ 1 1 2 3]
• Take modulo of each element in prefix sum and check k - if you get k - you can count 1 to ans - but how do you factor in (1-1) ⇒ 0 % 3 = k i.e 0 - how do find 1st index - 0th index - how do you find all such indexes efficiently

Core Mathematical Insight

For any subarray [l,r]:

count = prefix[r] - prefix[l-1]
We want: count % modulo == k
Therefore: (prefix[r] - prefix[l-1]) % modulo == k
Rearranging: prefix[l-1] % modulo == (prefix[r] - k + modulo) % modulo

Key Equation: (prefix[r] - k + modulo) % modulo == prefix[l-1] % modulo

You need to find prefix[l-1] % modulo , that can be achieved by finding (prefix[r] - k + modulo) % modulo

Algorithm Strategy

As we iterate through positions:

1. Known: prefix[r] (current position) and k (given)
2. Calculate: Target remainder = (prefix[r] - k + modulo) % modulo
3. Find: How many previous positions had this target remainder
4. Store: Current prefix[r] % modulo for future lookups

Complete Solution

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        int n = nums.size();
        
        // Step 1: Build prefix sum array
        vector<int> prefix_sum(n+1, 0);
        for(int i = 0; i < n; i++){
            prefix_sum[i+1] = prefix_sum[i] + ((nums[i] % modulo == k) ? 1 : 0);
        }
        
        // Step 2: Count using frequency map
        unordered_map<int,int> freq;
        long long result = 0;
        
        for(int i = 0; i <= n; i++){
            // Calculate what previous remainder we need
            int targetReminder = (prefix_sum[i] - k + modulo) % modulo;
            
            // Count how many previous positions had this remainder
            if(freq.find(targetReminder) != freq.end()){
                result += freq[targetReminder];
            }
            
            // Store current remainder for future lookups
            freq[prefix_sum[i] % modulo]++;
        }
        
        return result;
    }
};
 

Step-by-Step Explanation

Step 1: Convert to Binary and Build Prefix Sum

prefix_sum[i+1] = prefix_sum[i] + ((nums[i] % modulo == k) ? 1 : 0);

Purpose: Transform the problem into counting 1s in subarrays

• If nums[i] % modulo == k → contribute 1 to count
• Otherwise → contribute 0 to count
• prefix_sum[i] = count of interesting elements in nums[0...i-1]

Step 2: Core Loop Logic

int targetReminder = (prefix_sum[i] - k + modulo) % modulo;

Mathematical derivation:

• We want: (prefix[r] - prefix[l-1]) % modulo == k
• Rearranging: prefix[l-1] % modulo == (prefix[r] - k) % modulo
• Adding modulo for negative safety: (prefix[r] - k + modulo) % modulo

Step 3: Frequency Lookup

if(freq.find(targetReminder) != freq.end()){
    result += freq[targetReminder];
}

Purpose: Count all previous positions with the required remainder

• freq[remainder] stores how many positions had that remainder
• Each such position forms a valid subarray with current position

Step 4: Store Current Remainder

freq[prefix_sum[i] % modulo]++;

Purpose: Make current position available for future lookups

• Store prefix_sum[i] % modulo (not exact value!)
• Future iterations will search for this remainder

WHY???

(prefix[r] - k + modulo) % modulo == prefix[l-1] % modulo

Breakdown:

• Left side: (prefix[r] - k + modulo) % modulo - This is what we calculate (we know prefix[r] and k)
• Right side: prefix[l-1] % modulo - This is what we need to find

Why We Store prefix[i] % modulo at Each Step

        for(int i = 0; i <= n; i++){
            // Calculate what previous remainder we need
            int targetReminder = (prefix_sum[i] - k + modulo) % modulo;
            
            // Count how many previous positions had this remainder
            if(freq.find(targetReminder) != freq.end()){
                result += freq[targetReminder];
            }
            
            // Store current remainder for future lookups
            freq[prefix_sum[i] % modulo]++;
        }
}

The Logic Flow

At each position i:

1. Calculate target: (prefix[i] - k + modulo) % modulo
2. Look for: How many previous positions j had prefix[j] % modulo == target
3. Store: prefix[i] % modulo for future positions to find

Also why do we do (prefixr - k + modulo) % modulo instead, why we cannot just do (prefixr - k ) % modulo

The Problem with Negative Numbers

Example Where It Fails

Let’s say: prefix[r] = 1, k = 2, modulo = 3

Without + modulo:

(prefix[r] - k) % modulo = (1 - 2) % modulo = (-1) % 3

Problem: In C++, (-1) % 3 = -1 (negative result!)

With + modulo:

(prefix[r] - k + modulo) % modulo = (1 - 2 + 3) % 3 = 2 % 3 = 2

Time & Space Complexity

• Time: O(n) - single pass through array
• Space: O(modulo) - frequency map stores at most modulo different remainders

Key Takeaways

1. Transform to prefix sums to handle subarray counts efficiently
2. Use modular arithmetic to group equivalent prefix values
3. Store remainders, not exact values for efficient frequency counting
4. Add modulo to handle negative numbers in modular arithmetic
5. Look backwards while storing current state for future lookups