Leetcode 0974. Subarray Sums Divisible by K

Problem statement

https://leetcode.com/problems/subarray-sums-divisible-by-k/

Solution

All we need to do is to evaluate cumulative sums and then for every reminder d with frequency x evaluate number x * (x - 1)//2.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def subarraysDivByK(self, nums, k):
        acc = [0] + list(accumulate(nums))
        cnt = Counter()
        for x in acc:
            cnt[x%k] += 1
            
        return sum(x*(x-1)//2 for x in cnt.values())