Count of Interesting Subarrays

maind.md

Question

Approach

To solve the problem, I kept track of how many numbers so far satisfy nums[i] % modulo == k using a prefix count. At each position, I calculated the current prefix modulo and checked how many previous prefix sums would form an interesting subarray ending at the current index. I used a hashmap to record the frequency of each prefix modulo. By rearranging the modulo condition, I quickly found how many matches existed without checking every subarray. I updated the answer at each step and continued this process across the array.

Implementation

class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        prefix = 0
        count = defaultdict(int)
        count[0] = 1
        ans = 0

        for num in nums:
            if num % modulo == k:
                prefix += 1
            curr_mod = prefix % modulo
            target = (curr_mod - k + modulo) % modulo
            ans += count[target]
            count[curr_mod] += 1
        
        return ans

Complexities

• Time:
• Space: