Subarray Sums Divisible by K

This is the hardest problem in the section, and it is a close cousin of Subarray Sum Equals K. The difference is the condition: instead of "the sum is exactly k", it is "the sum is a multiple of k". That one change moves the question from values to remainders, and it brings in a trap that has nothing to do with algorithms — how the % operator treats negative numbers.

Interviewers like it as a follow-up to Subarray Sum Equals K because it tests whether you understood why the map worked, or only memorised the code.

The problem

Given a list of integers and a positive integer k, return how many contiguous, non-empty subarrays have a sum that is divisible by k.

• nums = [3, 1, 4, -2, 6], k = 3 → 6. The subarrays are [3], [6], [1, 4, -2] (sum 3), [3, 1, 4, -2] (sum 6), [1, 4, -2, 6] (sum 9) and the whole array (sum 12).
• nums = [-1, 3], k = 3 → 1. Only [3] works; −1 and 2 are not multiples of 3.

Constraints: 1 ≤ n ≤ 3 × 10⁴, values between −10⁴ and 10⁴, and 2 ≤ k ≤ 10⁴.

Clarifying questions

• Does a sum of 0 count? Yes; 0 is divisible by every k.
• Can values be negative? Yes — and that is where most bugs come from.
• Is k always positive? Assume yes. (If k could be 0, "divisible by 0" would need defining; ask.)
• Count, not list? Count.

Approach 1: the simple way

Every start, every end, with a running total.

1def subarrays_div_by_k_brute(nums: list[int], k: int) -> int:2    """Try every subarray, keeping a running total per start."""3    count = 04    for start in range(len(nums)):5        total = 06        for end in range(start, len(nums)):7            total += nums[end]8            if total % k == 0:9                count += 110    return count

Time is O(n²), space O(1). At n = 3 × 10⁴ there are about 4.5 × 10⁸ subarrays — close to a minute of Python, well past a one-second limit.

The key insight

A subarray from i to j has sum prefix[j + 1] - prefix[i]. That difference is divisible by k exactly when the two prefixes leave the same remainder when divided by k.

Why: write prefix[j + 1] = a × k + r1 and prefix[i] = b × k + r2, with both remainders between 0 and k − 1. The difference is (a − b) × k + (r1 − r2). It is a multiple of k only if r1 − r2 is, and two numbers between 0 and k − 1 can only differ by a multiple of k if they are equal.

So the question becomes: how many earlier prefixes share my current remainder? It is Subarray Sum Equals K again, with "remainder" in place of "value", and with running − k replaced by running itself.

Because remainders only take k values, a plain list of k counters replaces the hash map. The seed is the same idea as before: the empty prefix is 0, whose remainder is 0, so counts[0] starts at 1.

One more consequence: if a remainder appears c times among all n + 1 prefixes, it contributes c × (c − 1) / 2 subarrays — one for every pair. You can count at the end instead of along the way; both are O(n).

Approach 2: count remainders

1def subarrays_div_by_k(nums: list[int], k: int) -> int:2    """Count subarrays whose sum is a multiple of k."""3    counts = [0] * k4    counts[0] = 1               # the empty prefix has remainder 05    running = 06    answer = 07    for value in nums:8        running = (running + value) % k   # Python's % is never negative for k > 09        answer += counts[running]         # same remainder earlier = divisible gap10        counts[running] += 111    return answer

Keeping running as a remainder (instead of the full prefix) is safe, because (a + b) % k equals ((a % k) + b) % k. It also keeps the numbers small.

Dry run on nums = [3, 1, 4, -2, 6], k = 3

At i = 0, remainder 0 matches the seed: [3]. At i = 3, it matches the seed and index 0: [3, 1, 4, -2] and [1, 4, -2]. At i = 4, it matches three earlier zeros: the whole array, [1, 4, -2, 6] and [6]. Total 6.

The pair formula agrees: remainder 0 appears 4 times among the prefixes, giving 4 × 3 / 2 = 6, and remainders 1 and 2 appear once each, giving 0.

Complexity. Time is O(n) — one pass, O(1) per element. Space is O(k) for the counter list, independent of n.

Edge cases

• Negative numbers. Python's % with a positive k always returns a value from 0 to k − 1: -2 % 3 is 1. In Java, C++, C# and JavaScript, -2 % 3 is −2. There you must normalise: ((running + value) % k + k) % k. Without it, [-1, 3] with k = 3 gets remainders −1 and 2 — the same class, stored under different keys — and returns 0 instead of 1. With a list, a negative index crashes outright.
• k = 1. Every sum is divisible, so the answer is n(n + 1)/2: [1, 2, 3] → 6.
• Zeros. A 0 leaves the remainder unchanged, so it always creates matches: [0, 0] with any k gives 3.
• A single element. [4] with k = 2 → 1; [-3] with k = 3 → 1.

Saying it in the interview

Follow-ups

• "Is there a subarray of length at least 2 whose sum is a multiple of k?" Store the first index of each remainder (seeded {0: -1}) and return true when the same remainder appears again at least 2 positions later.
• "Count subarrays whose sum leaves remainder t." Look up (running - t) % k instead of running.
• "k can be 0." Then "divisible by 0" can only mean "sum equals 0", which is Subarray Sum Equals K with k = 0.