LeetCode 974: Subarray Sums Divisible by K

A clear explanation of counting subarrays whose sum is divisible by k using prefix sums and remainder frequencies.

leetcodearrayhash-tableprefix-sum

Problem Restatement

We are given an integer array nums and an integer k.

Return the number of non-empty contiguous subarrays whose sum is divisible by k.

A subarray is a continuous part of the array.

The official constraints are:

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

Source: LeetCode problem statement.

Input and Output

Item Meaning
Input Integer array nums
Input Integer k
Output Number of non-empty subarrays with sum divisible by k
Subarray Contiguous slice of the array

Example function shape:

def subarraysDivByK(nums: list[int], k: int) -> int:
    ...

Examples

Example 1:

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

Output:

7

The valid subarrays are:

[4, 5, 0, -2, -3, 1]
[5]
[5, 0]
[5, 0, -2, -3]
[0]
[0, -2, -3]
[-2, -3]

Example 2:

nums = [5]
k = 9

Output:

0

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

First Thought: Check Every Subarray

A direct solution is to try every subarray.

For each starting index, extend the ending index and keep a running sum.

answer = 0

for left in range(len(nums)):
    total = 0

    for right in range(left, len(nums)):
        total += nums[right]

        if total % k == 0:
            answer += 1

This avoids recomputing each subarray sum from scratch, but it still checks every possible subarray.

There are O(n^2) subarrays, which is too slow for n = 3 * 10^4.

Key Insight

Use prefix sums.

Let:

prefix[j] = nums[0] + nums[1] + ... + nums[j]

The sum of a subarray from i + 1 to j is:

prefix[j] - prefix[i]

This subarray sum is divisible by k when:

(prefix[j] - prefix[i]) % k == 0

That is equivalent to:

prefix[j] % k == prefix[i] % k

So two prefix sums with the same remainder form a subarray whose sum is divisible by k.

Why Remainder Counts Work

Suppose the current prefix sum has remainder r.

If we have already seen r exactly count[r] times, then each previous prefix with remainder r forms a valid subarray ending at the current position.

So we add:

count[r]

to the answer.

Then we record the current prefix remainder by incrementing:

count[r] += 1

We initialize:

count[0] = 1

This represents the empty prefix before the array starts.

It lets us count subarrays starting at index 0.

Algorithm

  1. Create a frequency array or dictionary for remainders.
  2. Set count[0] = 1.
  3. Set prefix = 0 and answer = 0.
  4. For each number x in nums:
    • Update the prefix remainder:
prefix = (prefix + x) % k
  • Add previous same-remainder count:
answer += count[prefix]
  • Record the current remainder:
count[prefix] += 1
  1. Return answer.

Negative Numbers

The array may contain negative numbers.

In Python, modulo already returns a nonnegative remainder when k is positive.

Example:

-2 % 5 == 3

So this line is safe in Python:

prefix = (prefix + x) % k

In some languages, % can return a negative remainder. In those languages, normalize with:

prefix = ((prefix + x) % k + k) % k

Correctness

We prove that the algorithm counts exactly the subarrays whose sum is divisible by k.

For any subarray ending at the current index, its sum can be written as the difference between the current prefix sum and some previous prefix sum.

This subarray sum is divisible by k exactly when the current prefix sum and that previous prefix sum have the same remainder modulo k.

The algorithm keeps count[r], the number of previous prefix sums with remainder r.

When the current prefix remainder is r, there are exactly count[r] previous prefixes that can pair with it to form a divisible subarray ending at the current index. The algorithm adds exactly this number to the answer.

Then it records the current prefix so future subarrays can use it.

The initial count[0] = 1 correctly represents the empty prefix, which allows subarrays starting at index 0 to be counted when their prefix sum is divisible by k.

Therefore, every valid subarray is counted once, at its ending index, and no invalid subarray is counted.

Complexity

Let n = len(nums).

Metric Value Why
Time O(n) We scan the array once
Space O(k) There are only k possible remainders

Implementation

class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        count = [0] * k
        count[0] = 1

        prefix = 0
        answer = 0

        for x in nums:
            prefix = (prefix + x) % k

            answer += count[prefix]
            count[prefix] += 1

        return answer

Code Explanation

We create one counter for each possible remainder:

count = [0] * k

Then initialize the empty prefix:

count[0] = 1

The running prefix remainder starts at 0:

prefix = 0

For each number:

prefix = (prefix + x) % k

we update the current prefix remainder.

If this remainder appeared before:

answer += count[prefix]

then each previous occurrence gives a valid subarray ending here.

Then we record the current prefix remainder:

count[prefix] += 1

Finally:

return answer

returns the total number of valid subarrays.

Testing

def run_tests():
    s = Solution()

    assert s.subarraysDivByK([4, 5, 0, -2, -3, 1], 5) == 7
    assert s.subarraysDivByK([5], 9) == 0

    assert s.subarraysDivByK([5], 5) == 1
    assert s.subarraysDivByK([0, 0, 0], 3) == 6
    assert s.subarraysDivByK([-1, 2, 9], 2) == 2
    assert s.subarraysDivByK([1, 2, 3, 4, 5], 3) == 7

    print("all tests passed")

run_tests()

Test meaning:

Test Why
[4,5,0,-2,-3,1], k = 5 Main example with negatives
[5], k = 9 No valid subarray
[5], k = 5 Single valid subarray
[0,0,0] Every subarray is valid
[-1,2,9] Negative number modulo behavior
[1,2,3,4,5] Multiple prefix remainder matches