Subarray Sums Divisible by K (LeetCode 974)

The problem

Given an integer array nums (values may be negative) and an integer k, return the number of non-empty contiguous subarrays whose sum is divisible by k.

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

The seven subarrays are [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3] and [-2,-3]; each sums to a multiple of 5.

How to think about it

Start with brute force. Check every subarray’s sum: O(n²) with a running sum per start. With n up to 3 × 10⁴, that is about 4.5 × 10⁸ checks, too slow.

The key insight: equal remainders cancel. A subarray nums[a+1..b] has sum pre[b] - pre[a]. That difference is divisible by k exactly when pre[a] and pre[b] leave the same remainder mod k. So you do not care about the prefix sums themselves, only their remainders.

Count, don’t list. Walk the array keeping the running remainder s. Every earlier prefix with the same remainder pairs with the current one to make a valid subarray, so add cnt[s] to the answer, then increment cnt[s]. Seed cnt[0] = 1 for the empty prefix, so subarrays starting at index 0 are counted.

Which pattern is this? Prefix sums plus a hash map of counts, the same as Subarray Sum Equals K. The tell is “count subarrays whose sum has some property”: here the property is “divisible by k”, which becomes “same remainder”.

Approach

1. Set cnt = {0: 1}, s = 0, res = 0.
2. For each x, update s = (s + x) % k.
3. Add cnt[s] to res: each earlier prefix with this remainder closes a divisible subarray here.
4. Increment cnt[s].
5. Return res.

Solution

from collections import defaultdict

def subarrays_div_by_k(nums, k):
    cnt = defaultdict(int); cnt[0] = 1; s = 0; res = 0   # empty prefix has remainder 0
    for x in nums:
        s = (s + x) % k; res += cnt[s]; cnt[s] += 1      # pair with every earlier same remainder
    return res
# subarrays_div_by_k([4,5,0,-2,-3,1], 5) -> 7

Dry run

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

The answer is 7.

Complexity

• Time: O(n). One pass, O(1) work per element.
• Space: O(k). There are at most k distinct remainders in the map.

Edge cases and pitfalls

• Negative numbers. In Python, -2 % 5 is 3, always non-negative, so the code is safe. In Java or C++, % can return a negative value; fix it with ((s % k) + k) % k, or equal remainders will look different.
• Forgetting cnt[0] = 1 misses every subarray that starts at index 0, such as the whole array in the example.
• Adding before incrementing matters: add cnt[s] first, then increment, or every prefix pairs with itself and you count empty subarrays.
• No valid subarray ([5] with k = 9) returns 0.

Related problems

• Subarray Sum Equals K (LeetCode 560): the same counting map, keyed by sum instead of remainder.
• Continuous Subarray Sum (LeetCode 523): the same remainder idea, but asks whether one of length at least 2 exists.
• Contiguous Array (LeetCode 525): equal prefix sums again, for the longest balanced stretch.