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))
|