Subarray Sums Divisible by K

The problem. Given an array of integers nums and an integer k, return the number of (non-empty) subarrays whose sum is divisible by k — a sum of 0, k, −k, 2k … all count.

The array 4, 5, 0, -2, -3, 1 with k = 5 has seven subarrays whose sum is divisible by 5: the whole array (5), 5, 5 0, 5 0 -2 -3 (0), 0, 0 -2 -3 (-5) and -2 -3 (-5).

Example

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

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 7 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++.

Still to come

1. Brute force: a running sum for every start
The key idea: equal remainders
2. Optimal: count remainders in a hash map
3. Best solution: an array of k counters
Comparing the approaches
Edge cases to test
Variations

Prev Next

Mark completed

Was this helpful?

ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems
StringsCharacter arrays with their own set of classic patterns — two pointers, sliding window, and more.19 lessons · 19 problems
QueueFirst-in, first-out — the structure behind task scheduling and breadth-first traversal.4 lessons · 5 problems

Subarray Sums Divisible by K

Example

Keep reading. It's free.

Keep exploring