Subarray Sums Divisible by K: Prefix Sums Meet Modular Arithmetic

LeetCode #974, Subarray Sums Divisible by K, is a counting problem that blends prefix sums with modular arithmetic. You are given an array of integers and a positive integer k, and you need to count how many contiguous subarrays have a sum divisible by k. The brute force approach checks every subarray in O(n^2), but a single mathematical observation about remainders gets you down to O(n).

The problem

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

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

A subarray is a contiguous, non-empty sequence of elements. The array can contain negative numbers, which means sliding window approaches will not work here.

Why remainders matter

Start by building a running prefix sum as you iterate through the array. The sum of any subarray from index i+1 to j is prefix[j] - prefix[i]. You want that difference to be divisible by k, which means prefix[j] % k == prefix[i] % k. In other words, two prefix sums with the same remainder mod k define a subarray whose sum is a multiple of k.

So the problem reduces to counting pairs of prefix sums that share the same remainder. If a particular remainder has appeared c times so far, and the current prefix sum has that same remainder, then there are c new valid subarrays ending at the current index. You add c to your answer, then increment the frequency.

Handling negative remainders

There is one subtle detail. In languages like Java or C++, the modulo operator can return negative values when the dividend is negative. For example, (-3) % 5 might return -3 instead of 2. You need to normalize the remainder to always be in the range [0, k-1]. In Python, the % operator already returns non-negative results for a positive divisor, so no extra handling is needed. In other languages, use ((prefix_sum % k) + k) % k to guarantee a non-negative remainder.

Step-by-step walkthrough

Let us trace through nums = [4, 5, 0, -2, -3, 1] with k = 5.

The algorithm finds all 7 subarrays with sums divisible by 5: [5], [5,0], [0], [5,0,-2,-3], [0,-2,-3], [-2,-3], and [4,5,0,-2,-3,1].

The code

from collections import defaultdict

def subarraysDivByK(nums, k):
    remainder_count = defaultdict(int)
    remainder_count[0] = 1
    prefix_sum = 0
    count = 0

    for num in nums:
        prefix_sum += num
        remainder = prefix_sum % k
        count += remainder_count[remainder]
        remainder_count[remainder] += 1

    return count

Here is how it works:

1. Seed the map with {0: 1}. Before processing any element, the prefix sum is 0, which has remainder 0. If a later prefix sum also has remainder 0, the subarray from the start to that position has a sum divisible by k. The seed ensures we count those subarrays.

2. Accumulate the prefix sum. For each element, add it to the running total.

3. Compute the remainder. Take prefix_sum % k. This tells you the equivalence class of the current prefix sum under modular arithmetic.

4. Add the frequency to count. If this remainder has been seen c times before, then c subarrays ending here have a sum divisible by k. Add c to the result.

5. Increment the frequency. Record that this remainder has been seen one more time, so future elements can reference it.

The order matters: check the map before updating it, so you never count a zero-length "subarray" by matching a prefix sum against itself.

Complexity analysis

Time: O(n). You iterate through the array once. Each hash map lookup and insertion is O(1) on average, so the total work is linear.

Space: O(min(n, k)). The hash map stores remainder frequencies. There are at most k distinct remainders (0 through k-1). If n is smaller than k, you store at most n + 1 entries. Either way, space is bounded by the smaller of n and k.

The building blocks

Prefix sum with modular arithmetic

prefix_sum = 0
for num in nums:
    prefix_sum += num
    remainder = prefix_sum % k

This extends the standard prefix sum with a modulo operation. The prefix sum itself can grow arbitrarily large, but you only care about the remainder. Two prefix sums with the same remainder produce a subarray sum that is divisible by k. This pattern applies to any problem involving subarray sums and divisibility conditions.

Frequency-based hash map

count += remainder_count[remainder]
remainder_count[remainder] += 1

Unlike the Continuous Subarray Sum problem (LeetCode #523), which stores the first index where each remainder appears, this problem uses a frequency count. The reason: you need to count all valid subarrays, not just detect whether one exists. Each time you see a remainder that appeared c times before, you gain c new valid subarrays. The frequency map captures exactly this information.

Edge cases

• Single element divisible by k. For nums = [5] and k = 5, the prefix sum is 5 with remainder 0. The map already has {0: 1} from the seed, so count = 1. Correct.
• Single element not divisible by k. For nums = [5] and k = 9, the prefix sum is 5 with remainder 5. Not in the map. count = 0. Correct.
• All zeros. Every prefix sum has remainder 0. The frequency keeps climbing: at index i, the map has {0: i+1}, and you add i+1 to the count. The total is n * (n + 1) / 2, counting every possible non-empty subarray.
• Negative numbers. The prefix sum can decrease. In Python, (-3) % 5 gives 2, so remainders stay non-negative. In Java or C++, you need to normalize: ((prefix_sum % k) + k) % k.
• k = 1. Every integer is divisible by 1, so every non-empty subarray is valid. Every remainder is 0, and the frequency map at {0} grows on each step. The total is n * (n + 1) / 2.
• Large k. If k is larger than the sum of all elements, remainders can still repeat. The algorithm does not make assumptions about the relationship between k and the array values.

From understanding to recall

The prefix sum + modular arithmetic + hash map combination is a pattern that shows up repeatedly in subarray problems. The core idea is always the same: reframe a subarray sum condition as a relationship between prefix sums, then use a hash map to check that relationship in O(1). The twist here is that instead of looking for an exact difference (as in Subarray Sum Equals K), you look for matching remainders.

Spaced repetition helps you internalize the differences between these closely related problems. After a few review cycles, you will instantly recognize whether a problem calls for a frequency count (this problem) or a first-occurrence map (Continuous Subarray Sum). That kind of precision is what separates recognizing a pattern from executing it cleanly under interview pressure.

Related posts

• Subarray Sum Equals K - Same prefix sum approach but checking for exact sums
• Continuous Subarray Sum - Also uses prefix sums with modular arithmetic
• Maximum Subarray - Another subarray optimization using Kadane's algorithm

CodeBricks uses spaced repetition to help you internalize patterns like prefix sum + hash map. Instead of re-reading solutions, you practice writing them from scratch at increasing intervals. Each review strengthens the connection between "divisible by k" and "matching remainders in a frequency map." Over time, the pattern becomes second nature.