Subarray Sums Divisible by K

Prefix SumHash Map

25 min

Problem Statement

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

Example

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5

nums: [4, 5, 0, -2, -3, 1], k: 5

Output: 7

Solution

This problem is a variation of "Continuous Subarray Sum". We use a hash map to store the frequency of prefix sum remainders. If we find a remainder that has occurred before, it means the sum of the elements between the two occurrences is a multiple of `k`.

Algorithm Steps

Initialize a hash map `remainder_map` with a remainder of 0 having a frequency of 1.
Initialize `prefixSum` and `count` to 0.
Iterate through the array.
Update `prefixSum` and calculate the remainder.
If the remainder is in the map, add its frequency to `count`.
Increment the frequency of the current remainder in the map.
Return `count`.

Subarray Sums Divisible by K

Prefix Sum with Hash Map

Input: nums = [4, 5, 0, -2, -3, 1], k = 5

Output: 0

Progress1 / 1

Ready to start the visualization

Nums

-2

-3

Remainder Map

0: 1

Subarray Sums Divisible by K Solution


class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        res = 0
        prefix_sum = 0
        count = {0: 1}
        
        for n in nums:
            prefix_sum += n
            rem = prefix_sum % k
            if rem in count:
                res += count[rem]
            count[rem] = 1 + count.get(rem, 0)
        return res