BinarySearch 0642 Number of K-Divisible Sublists

Problem statement

https://binarysearch.com/problems/Number-of-K-Divisible-Sublists/

Solution

Equal to Leetcode 0974. Subarray Sums Divisible by K.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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())