[Leetcode] 2845. Count of Interesting Subarrays (retry i dont get it)

https://leetcode.com/problems/count-of-interesting-subarrays/description/?envType=daily-question&envId=2025-04-25

initial

I really didnt know except first forming an intermediary list for easier calculation. But we first need to udnerstand some maths

We can use a prefix sum value acc to count how many numbers can % mod to give value k. So acc at index i represents the remainder of the count of "interesting" elements in the prefix subarray nums[0...i] when divided by modulo.

As we discussed, for a subarray nums[l...r], the count cnt of interesting elements is related to the prefix sums acc:

cnt=(count up to r)−(count up to l−1)
but cnt also has to be cnt % mod = k, and using this a(% m)==b(% m) theory, cnt≡k(% mod).

substitute, we get
(acc[r]−acc[l−1])≡k(modmodulo)
This implies that the remainder of (acc[r]−acc[l−1]) when divided by modulo must be equal to k.
So that is why we should add

res += count[(acc - k) % mod]

solution

from collections import Counter
class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        res = acc = 0
        count = Counter({0:1})
        for num in nums:
            acc = (acc + (1 if num % modulo ==k else 0)) % modulo
            res += count[(acc-k) % modulo]
            count[acc]+=1
        return res
        

complexity

n time and modulo space cuz counter stores modulo number of keys (e.g. 0~2 keys if modulo is 2)