1
# Runtime: 209 ms (Top 98.8%) | Memory: 16.64 MB (Top 51.7%)
2

3

4
class Solution:
5
    def subarraysDivByK(self, nums, k):
6
        n = len(nums)
7
        prefix_mod = 0
8
        result = 0
9

10
        # There are k mod groups 0...k-1.
11
        mod_groups = [0] * k
12
        mod_groups[0] = 1
13

14
        for num in nums:
15
            # Take modulo twice to avoid negative remainders.
16
            prefix_mod = (prefix_mod + num % k + k) % k
17
            # Add the count of subarrays that have the same remainder as the current
18
            # one to cancel out the remainders.
19
            result += mod_groups[prefix_mod]
20
            mod_groups[prefix_mod] += 1
21

22
        return result