LeetCode 974: Subarray Sums Divisible by K

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:

Source: LeetCode problem statement.

Input and Output

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

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

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: