Problem Description

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 considered interesting if it satisfies the following condition:

• Count how many indices i in the range [l, r] have the property that nums[i] % modulo == k. Let's call this count cnt.
• The subarray is interesting if cnt % modulo == k.

In other words, you need to:

1. For each subarray, count how many elements in that subarray leave remainder k when divided by modulo
2. Check if this count itself leaves remainder k when divided by modulo
3. If yes, the subarray is interesting

Return the total number of interesting subarrays in the array.

Note: A subarray is a contiguous non-empty sequence of elements within an array.

Example to clarify: If nums = [3, 2, 4], modulo = 2, and k = 1:

• For subarray [3]: one element where 3 % 2 = 1 (equals k), so cnt = 1. Since 1 % 2 = 1 (equals k), this subarray is interesting.
• For subarray [3, 2]: only one element where 3 % 2 = 1, so cnt = 1. Since 1 % 2 = 1, this subarray is interesting.
• For subarray [2, 4]: zero elements satisfy the condition, so cnt = 0. Since 0 % 2 = 0 (not equal to k), this subarray is not interesting.

Intuition

The key insight is to transform this problem into a simpler one using prefix sums and modular arithmetic.

First, let's simplify what we're counting. Instead of working with the original array, we can create a binary array where each position is 1 if nums[i] % modulo == k, and 0 otherwise. Now the problem becomes: find subarrays where the sum of elements (count of 1s) satisfies sum % modulo == k.

For any subarray [l, r], the count of 1s equals prefix_sum[r] - prefix_sum[l-1]. We want this difference to satisfy: (prefix_sum[r] - prefix_sum[l-1]) % modulo == k

Rearranging this equation using modular arithmetic: prefix_sum[r] % modulo - prefix_sum[l-1] % modulo ≡ k (mod modulo)

This means: prefix_sum[r] % modulo ≡ (prefix_sum[l-1] % modulo + k) % modulo

Or equivalently: prefix_sum[l-1] % modulo ≡ (prefix_sum[r] % modulo - k) % modulo

This reveals the pattern: for each position r, we need to count how many previous positions l-1 have a prefix sum that, when taken modulo modulo, equals (current_prefix_sum - k) % modulo.

This naturally leads to using a hash table to track the frequency of each prefix_sum % modulo value as we traverse the array. For each position, we:

1. Check how many previous prefix sums would make a valid subarray ending here
2. Add the current prefix sum modulo value to our frequency map

We initialize with cnt[0] = 1 to handle subarrays starting from index 0, where the "previous" prefix sum is considered to be 0.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation follows the prefix sum with hash table pattern:

Step 1: Transform the array

arr = [int(x % modulo == k) for x in nums]

We create a binary array arr where arr[i] = 1 if nums[i] % modulo == k, otherwise arr[i] = 0. This transformation simplifies our problem to counting subarrays with a specific sum property.

Step 2: Initialize the hash table

cnt = Counter()
cnt[0] = 1

We use a hash table cnt to track the frequency of prefix_sum % modulo values. Initialize cnt[0] = 1 to handle subarrays that start from index 0.

Step 3: Traverse and count

ans = s = 0
for x in arr:
    s += x
    ans += cnt[(s - k) % modulo]
    cnt[s % modulo] += 1

For each element in the transformed array:

• Update the prefix sum s by adding the current element
• Look up how many previous prefix sums would create a valid subarray ending at the current position. We need prefix sums that satisfy (s - prefix_sum) % modulo == k, which means we look for prefix_sum % modulo == (s - k) % modulo
• Add this count to our answer
• Update the hash table with the current prefix sum modulo value for future positions to use

The key insight is that (s - k) % modulo gives us the required remainder that previous prefix sums must have for the subarray to be interesting.

Time Complexity: O(n) where n is the length of the array, as we traverse once.

Space Complexity: O(min(n, modulo)) for the hash table, which stores at most modulo different remainder values.

Example Walkthrough

Let's walk through with nums = [3, 2, 4], modulo = 2, k = 1.

Step 1: Transform the array

• Check each element: does nums[i] % 2 == 1?
• 3 % 2 = 1 ✓, 2 % 2 = 0 ✗, 4 % 2 = 0 ✗
• Transformed array: arr = [1, 0, 0]

Step 2: Initialize

• cnt = {0: 1} (to handle subarrays from start)
• ans = 0, s = 0 (prefix sum)

Step 3: Process each element

Index 0 (arr[0] = 1):

• Update prefix sum: s = 0 + 1 = 1
• Look for previous prefix sums with remainder (1 - 1) % 2 = 0
• cnt[0] = 1, so add 1 to answer: ans = 1
• Update cnt: cnt[1 % 2] = cnt[1] += 1
• State: cnt = {0: 1, 1: 1}, ans = 1

Index 1 (arr[1] = 0):

• Update prefix sum: s = 1 + 0 = 1
• Look for previous prefix sums with remainder (1 - 1) % 2 = 0
• cnt[0] = 1, so add 1 to answer: ans = 2
• Update cnt: cnt[1 % 2] = cnt[1] += 1
• State: cnt = {0: 1, 1: 2}, ans = 2

Index 2 (arr[2] = 0):

• Update prefix sum: s = 1 + 0 = 1
• Look for previous prefix sums with remainder (1 - 1) % 2 = 0
• cnt[0] = 1, so add 1 to answer: ans = 3
• Update cnt: cnt[1 % 2] = cnt[1] += 1
• State: cnt = {0: 1, 1: 3}, ans = 3

Result: 3 interesting subarrays

Verification:

1. [3] (indices 0-0): cnt=1, 1 % 2 = 1 ✓
2. [3,2] (indices 0-1): cnt=1, 1 % 2 = 1 ✓
3. [3,2,4] (indices 0-2): cnt=1, 1 % 2 = 1 ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Creating the arr list requires a single pass through nums with O(n) time
• The main loop iterates through each element in arr exactly once, which is O(n)
• Inside the loop, all operations (addition, dictionary lookup, dictionary insertion, modulo operation) are O(1)
• Therefore, the overall time complexity is O(n)

The space complexity is O(n). This is due to:

• The arr list stores n elements, requiring O(n) space
• The cnt Counter (dictionary) can store at most min(n+1, modulo) distinct keys, since we're storing values modulo modulo. In the worst case, this is O(n) when modulo >= n+1
• Other variables (ans, s, x) use O(1) space
• Therefore, the overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Modulo Operation for Negative Numbers

The most critical pitfall in this solution is handling the modulo operation when computing (current_prefix_sum - k) % modulo. In Python, the modulo operation handles negative numbers correctly (always returns non-negative results), but this behavior varies across programming languages.

Problem Example:

• If current_prefix_sum = 1, k = 3, modulo = 5
• (1 - 3) % 5 should give us 3 (the correct mathematical result)
• In Python: (-2) % 5 = 3 ✓
• In Java/C++: (-2) % 5 = -2 ✗

Solution: For languages that don't handle negative modulo correctly, use:

target_remainder = ((current_prefix_sum - k) % modulo + modulo) % modulo

2. Forgetting to Initialize the Hash Table with cnt[0] = 1

Without initializing cnt[0] = 1, subarrays starting from index 0 won't be counted correctly.

Problem Example:

• nums = [3], modulo = 2, k = 1
• The entire array [3] should be counted as interesting
• Without cnt[0] = 1, this subarray would be missed

Solution: Always initialize the counter with cnt[0] = 1 before processing any elements.

3. Using the Wrong Target Calculation

A common mistake is looking for (s + k) % modulo instead of (s - k) % modulo.

Problem Example: The relationship is: (current_sum - previous_sum) % modulo == k This rearranges to: previous_sum % modulo == (current_sum - k) % modulo

Using addition instead would look for the wrong prefix sums and produce incorrect results.

Solution: Remember the mathematical relationship: we're looking for prefix sums where the difference equals k modulo modulo, so we subtract k from the current sum.

4. Updating Hash Table Before Counting

If you update cnt[current_prefix_sum % modulo] before checking cnt[(current_prefix_sum - k) % modulo], you might incorrectly count single-element subarrays when k == 0.

Problem Example:

• When k = 0 and the current element satisfies the condition
• If we update first, we'd count the current position as both start and end of a subarray

Solution: Always follow the order:

1. Count valid subarrays using current state
2. Update the hash table with current prefix sum