974. Subarray Sums Divisible by K

974

MediumArrays and HashingPrefix sum modulo k with a hash mapPrefix remainder frequency counting

Subarray Sums Divisible by K

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

Open official problem prompt ↗

In plain English

Count how many contiguous subarrays have a sum that is an exact multiple of k.

Picture it like this

Imagine a clock with k positions. Each element advances the hand by its value. Whenever the hand lands on a position it has visited before, the moves in between summed to a full number of loops, i.e. a multiple of k.

Example

Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7
Why: The seven subarrays with sum divisible by 5 are: [4,5,0,-2,-3], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], and [-2,-3].

Constraints

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

Pattern lesson

See the pattern, then code

Prefix remainder frequency counting

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. A subarray sum is divisible by k exactly when the two prefix sums bounding it share the same remainder mod k. So count how many earlier prefixes had each remainder and, at each step, add the count for the current remainder.

New words, made simpleKnow these before the algorithm

Remainder class: The value prefixSum mod k; two prefixes in the same class bound a divisible subarray.
Non-negative modulo: Python's % operator returns a result with the sign of the divisor, so (negative) % k is already in [0, k), avoiding manual adjustment.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

All subarrays

Quadratic; too slow at n = 3*10^4.

Enumerate every subarray and test its sum mod k.

Time O(n^2)Space O(1)

Best choicePrefix remainder counting

Linear single pass; the standard optimal solution.

Group prefix sums by remainder mod k and count same-remainder pairs on the fly.

Time O(n)Space O(k)

The rule we keep true

Invariant

Before processing index i, counts[r] equals the number of prefixes ending before i whose sum mod k equals r (including the empty prefix, seeded as counts[0] = 1).

Why this is correct

Reasoning

The sum of elements from index a to b equals prefix[b] - prefix[a-1]; it is divisible by k iff prefix[b] mod k == prefix[a-1] mod k. Adding counts[prefix] before incrementing counts exactly tallies, for each right endpoint, how many earlier left boundaries share its remainder, so the running total equals the number of divisible subarrays. The seed {0:1} accounts for subarrays that start at index 0.

The algorithm in three movesSay these aloud before coding

1Track a running prefix sum reduced mod k, and a frequency map seeded with {0: 1}

remainders seen: 4,4,4,2,4,0

2At each element update prefix = (prefix + x) % k, which stays non-negative in Python

counts[4] grows: 1,2,3,...

3Add the current count of that remainder to the result (each earlier match forms a valid subarray)

result accumulates to 7

4Increment the frequency of the current remainder

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readprefix=4%5=4

2 · Askcounts[4]?

3 · Update statecounts={0:1}

4 · Resultresult += 0; counts[4]=1

Key takeaway

The running prefix remainders (mod 5) for each index; repeats of a remainder each contribute a divisible subarray.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-7Seed the empty prefix
counts[0] = 1 represents the prefix before any element, so subarrays starting at index 0 are counted.
2
Lines 9-12Count then record
Reduce the prefix mod k, add matches seen so far, then bump the remainder's frequency; the order ensures we never pair a prefix with itself.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Negative numbers, where Python's non-negative % is essential (a manual (x % k + k) % k is needed in languages like Java)
A single element divisible by k -> counts that length-1 subarray
Zeros in the array, which keep the remainder unchanged and pair with prior matches
No divisible subarray -> return 0

Common beginner mistakes

Not seeding counts[0] = 1, which drops all subarrays beginning at index 0
Incrementing the remainder's count before adding to the result, which wrongly pairs a prefix with itself
Assuming a language's % handles negatives like Python; many return negative remainders and need normalization
Confusing this with the equal-count problem (525), which stores first indices for max length rather than frequencies for a count

Check your understanding

Why does the order 'add counts[prefix] then increment' matter?

Subarray Sums Divisible by K

Subarray Sums Divisible by K

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing