aboutsummaryrefslogtreecommitdiff
path: root/subarr_sums_div_k.py
blob: c946fc70117a1a6ed26fc812dc21eb453ca406e7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 974. Subarray Sums Divisible by K

"""
given an integer array 'nums' and an integer 'k', return the number of non
empty subarrays that have a sum divisible by 'k'. a subarray is contiguous
part of an array.
"""


class Solution(object):
    def subarraysDivByK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        ans, prefix = 0, 0
        cnt = [1] + [0] * k
        for i in nums:
            prefix = (prefix + i) % k
            ans += cnt[prefix]
            cnt[prefix] += 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.subarraysDivByK(nums=[4, 5, 0, -2, -3, 1], k=5))
    print(obj.subarraysDivByK(nums=[5], k=9))