How do you approach Subarray Sums Divisible by K?

A subarray (i, j] is divisible by k exactly when prefix[j] and prefix[i] leave the SAME remainder mod k.

What is the time complexity of Subarray Sums Divisible by K?

Time complexity: O(n). Space complexity: O(k) for the remainder counts..

What are common mistakes on Subarray Sums Divisible by K?

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0. Counting the current prefix before checking for its complement, so a zero-sum range matches itself. Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.

gitGood.dev

← Back to problems

Subarray Sums Divisible by K

MediumAlgorithms

Description

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

A subarray is a contiguous slice of the array. Note that nums may contain negative numbers, which is where most incorrect solutions break.

Example 1

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

Output: 7

Example 2

Input: nums = [5], k = 9

Output: 0

Example 3

Input: nums = [1,2,3], k = 1

Output: 6

Constraints

- 1 <= nums.length <= 3 * 10^4 - -10^4 <= nums[i] <= 10^4 - 2 <= k <= 10^4 - An O(n^2) solution over every subarray is too slow at the upper bound.

Subarray Sums Divisible by K: approach, complexity and pitfalls

A medium prefix sum problem, graded against 6 test cases (3 of them hidden).

The pattern: Prefix Sum

Precomputed cumulative totals so any range query becomes one subtraction.

Reach for it when you see: Repeated range-sum queries, or counting subarrays that sum to a target.

If you are stuck

Show the 3-step hint ladder

A subarray (i, j] is divisible by k exactly when prefix[j] and prefix[i] leave the SAME remainder mod k.
So count prefix remainders in a map and, for each new prefix, add the number of earlier prefixes sharing its remainder. Seed the map with remainder 0 seen once (the empty prefix).
In JavaScript, (-3) % 5 is -3, not 2. Normalize with ((x % k) + k) % k. Python's % already returns a non-negative result for a positive k.

The optimal approach

Show the approach: Counting remainders, not sums

The sum of the subarray `(i, j]` is `prefix[j] - prefix[i]`. That difference is divisible by `k` precisely when the two prefixes are congruent mod `k`. So the problem reduces to: how many pairs of prefix sums share a remainder?

Sweep once, maintaining a running remainder and a count of how many times each remainder has been seen. At each step, every earlier prefix with the same remainder forms a valid subarray ending here, so add that count before recording the current one. Seed the counter with remainder `0` at count `1` to represent the empty prefix - that is what lets subarrays starting at index 0 be counted.

The negative-number trap. In JavaScript (and C, Java, Go), `%` takes the sign of the dividend: `-3 % 5` is `-3`, so `-3` and `2` land in different buckets even though they are the same residue class, and the count comes out low. Normalizing with `((x % k) + k) % k` fixes it. Python's `%` is already floor-based and returns a non-negative result when `k > 0`, which is why the same algorithm ported from Python to JavaScript silently breaks.

Time: O(n)
Space: O(k) for the remainder counts.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Prefix Sum mistakes

These apply to the pattern as a whole, not just this problem.

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0.
Counting the current prefix before checking for its complement, so a zero-sum range matches itself.
Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.