Problem description:

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 a contiguous part of an array.

Example 1:

1
2
3
4
Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

1
2
Input: nums = [5], k = 9
Output: 0

Constraints:

  • 1 <= nums.length <= 3 * 104
  • 104 <= nums[i] <= 104
  • 2 <= k <= 104

Solution:

1
2
3
4
5
6
7
8
Input:  A = [4,5,0,-2,-3,1], K = 5
          Map
step 1 : {0:1}          a=4    sum=4  mod=4  count = 0+0 =0
step 2 : {0:1,4:1}      a=5    sum=9  mod=4  count = 0+1 =1
step 3 : {0:1,4:2}      a=0    sum=9  mod=4  count = 1+2 =3
step 4 : {0:1,4:3}      a=-2   sum=7  mod=2  count = 3+0 =3
step 6 : {0:1,4:3,2:1}  a=-3   sum=4  mod=4  count = 3+3 =6
step 7 : {0:1,4:4,2:1}  a=1    sum=5  mod=0  count = 6+1 =7

For negative modulo

1
2
3
4
5
It's calculated exactly like the mod of a positive number. 
In arithmetic modulo 𝑐, we seek to express any 𝑥 as 𝑞𝑐+𝑟, where 𝑟 must be a 
non-negative integer.

Take −100 mod 8=4. This is because 8⋅−13=−104. The remainder is 4.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefix = defaultdict(int)
        res, cur_sum = 0, 0
        prefix[0] = 1
        for n in nums:
            cur_sum = (cur_sum+n)%k
            
            if cur_sum < 0:
                cur_sum += k
            res += prefix[cur_sum]
            prefix[cur_sum] += 1
        return res

We actually only need array with size k

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefix = [0 for i in range(k)]
        res, cur_sum = 0, 0
        prefix[0] = 1
        for n in nums:
            cur_sum = (cur_sum+n)%k
            
            if cur_sum < 0:
                cur_sum += k
            res += prefix[cur_sum]
            prefix[cur_sum] += 1
        return res

time complexity: $O(n)$
space complexity: $O(k)$
reference:
related problem: