BinarySearch 0582 K-Divisible Sublist

Problem statement

https://binarysearch.com/problems/K-Divisible-Sublist/

Solution

Variation of Leetcode 0974. Subarray Sums Divisible by K. We can calculate number of sublist and check that it is greater than number of lists with length 1.

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()) > sum(x%k == 0 for x in nums)