Subarray Sums Divisible by K — Medium Problem & Solution

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

Difficulty: Medium
Topics: Arrays, Hash Table, Prefix Sum
Asked at: Amazon, Google, Goldman Sachs
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

Example 1

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: Seven subarrays have a sum that is a multiple of 5, including the whole array and the single 0.

Example 2

Input: nums = [5], k = 9
Output: 0

Example 3

Input: nums = [-1,2,9], k = 2
Output: 2
Explanation: [2] and [-1,2,9].

Constraints

1 <= nums.length <= 30000
-10000 <= nums[i] <= 10000
2 <= k <= 10000

How to solve Subarray Sums Divisible by K

Reduce the prefix sums modulo k. Two prefixes with the same remainder bracket a subarray divisible by k, so the answer is the number of equal-remainder pairs.

Approach

Start a remainder tally with count[0] = 1, standing for the empty prefix.
Sweep the array keeping the running prefix sum reduced mod k (normalised to be non-negative).
Before recording the current remainder, add its existing tally to the answer — those are all the earlier prefixes that pair with this one.
Increment the tally and continue.

Why it works

(P[j] - P[i]) % k == 0 is the same as P[j] % k == P[i] % k, so counting pairs of equal remainders counts exactly the qualifying subarrays. Seeding count[0] = 1 is what lets subarrays starting at index 0 be found.

Complexity

Time — O(n)
Space — O(k)

Pitfalls

Forgetting the count[0] = 1 seed drops every subarray that starts at the beginning.
In C, Java, Go and friends -3 % 5 is -3, not 2 — the double-modulo normalisation is mandatory.
Adding the tally after incrementing it counts a prefix as pairing with itself.

Reference solution

Python

from typing import List

def subarraysDivByK(nums: List[int], k: int) -> int:
    count = {0: 1}
    total = 0
    s = 0
    for x in nums:
        s = (s + x) % k
        total += count.get(s, 0)
        count[s] = count.get(s, 0) + 1
    return total

JavaScript

var subarraysDivByK = function(nums, k) {
    var count = {};
    count["0"] = 1;
    var sum = 0, total = 0;
    for (var i = 0; i < nums.length; i++) {
        sum = ((sum + nums[i]) % k + k) % k;
        var key = String(sum);
        if (count[key] !== undefined) total += count[key];
        count[key] = (count[key] === undefined ? 0 : count[key]) + 1;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue