Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Replace each element conceptually with one if its remainder equals k, otherwise zero. A subarray is interesting when the sum of these indicators is congruent to k modulo m. Prefix counts turn that condition into a lookup for an earlier prefix remainder.

Approach

Initialize remainder-zero frequency to one for the empty prefix. Scan values, increasing the prefix count only when value % m == k. Add the frequency of (prefixCount - k) mod m to the answer, using a normalized remainder, then record the current prefix remainder. Looking up before recording avoids counting an empty subarray when k is zero. Return the accumulated count.

class Solution:
    def countInterestingSubarrays(self, nums: List[int], m: int, k: int) -> int:
        map = defaultdict(int)
        map[0] = 1
        pre = 0
        res = 0

        for n in nums:
            if n % m == k:
                pre += 1
            res += map[(pre - k) % m]
            map[pre % m] += 1

        return res

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(min(n, modulo)) for prefix-residue frequencies.