LC-0974 Medium LeetCode

974. Subarray Sums Divisible by K

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 56% Topics: Array, Hash Table, Prefix Sum

Reading material

Arrays & Hashing 12 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(k)

import collections


class Solution(object):
    def subarraysDivByK(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        count = collections.defaultdict(int)
        count[0] = 1
        result, prefix = 0, 0
        for a in A:
            prefix = (prefix+a) % K
            result += count[prefix]
            count[prefix] += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT