MediumArrayHash TablePrefix Sum

Subarray Sums Divisible by K

1 approach, code in every language

You are given an integer array nums and an integer k. Return the number of contiguous subarrays whose element sum is divisible by k.

Because the array can contain negative numbers, take care to normalize remainders into the range [0, k) so that two prefixes that are congruent modulo k are grouped together correctly.

Example 1

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

Output: 7

There are seven subarrays with a sum divisible by 5, including the whole array [4,5,0,-2,-3,1] and the singleton subarrays [5] and [0].

Example 2

Input: nums = [5], k = 9

Output: 0

The only subarray is [5], whose sum 5 is not divisible by 9.

Constraints

1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
2 <= k <= 10^4

Prefix Sum Remainders with Hash Map

Track the running prefix sum modulo k and count pairs of positions that share the same remainder, since equal remainders bound a divisible subarray.

Loading animation…

Intuition

The sum of the subarray from index i to j equals prefix[j] - prefix[i - 1]. That difference is divisible by k exactly when prefix[j] and prefix[i - 1] leave the same remainder modulo k, because their difference then clears out to a multiple of k. So instead of tracking exact prefix sums, we only need their remainders. We keep a frequency table of how many earlier prefixes produced each remainder; whenever we reach a remainder we have seen before, each earlier occurrence forms a valid subarray with the current position. Negative sums must be normalized with ((r % k) + k) % k so that, for example, -1 and k - 1 land in the same bucket. Seeding remainder 0 with a count of one accounts for prefixes that are themselves divisible by k.

Algorithm walkthrough

1Create a frequency array (or map) of size k, initialize it so remainder 0 has count 1, and set the running sum and answer to 0.
2Walk through nums, adding each value to the running sum.
3Compute the normalized remainder r = ((running % k) + k) % k so negative running sums map into [0, k).
4Add the current count of remainder r to the answer, since each earlier prefix with the same remainder marks a divisible subarray, then increment the count of r.
5After the pass, the accumulated answer is the number of subarrays whose sum is divisible by k.

Implementation

class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        counts = [0] * k
        counts[0] = 1
        running = 0
        answer = 0
        for num in nums:
            running += num
            r = ((running % k) + k) % k
            answer += counts[r]
            counts[r] += 1
        return answer

Time

O(n)

Space

O(k)

A single pass over nums; the counts table holds one bucket per possible remainder.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Full Turn Command Blocks is our own problem on the technique behind Subarray Sums Divisible by K: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free