Subarray Sum Divisible by K — Prefix Sum Modulo (LC 974)

Problem Statement#

LeetCode 974 — Subarray Sums Divisible by K (Medium)

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

Constraints:

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

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

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

Why This Problem Matters#

This problem is a canonical example of the prefix sum + hash map technique applied to divisibility. It requires two independent insights: (1) prefix sums convert a subarray sum query into a difference of two prefix values; (2) modular arithmetic converts divisibility into a remainder-equality condition.

The resulting algorithm is elegant: count pairs of prefix sums with equal remainders modulo k. Each such pair corresponds to a subarray whose sum is divisible by k. This pattern is the foundation for LC 560, LC 523, and dozens of variations involving modular conditions on subarray sums. Understanding it deeply is non-negotiable for senior-level interview performance.

The presence of negative numbers adds an important wrinkle: negative remainders must be normalised to [0, k-1] using ((prefix % k) + k) % k. Missing this normalisation is the single most common bug.

The Core Insight#

Let prefix[i] = nums[0] + ... + nums[i-1] (with prefix[0] = 0). Sum of nums[i..j] = prefix[j+1] - prefix[i].

Divisibility condition: (prefix[j+1] - prefix[i]) % k == 0 iff prefix[j+1] % k == prefix[i] % k.

Count pairs with equal remainders: maintain cnt[r] — how many times remainder r has been seen. For each new prefix sum:

1. Compute r = prefix % k (normalised)
2. Add cnt[r] to answer (all previous positions with same remainder form valid subarrays)
3. Increment cnt[r]

Initialise cnt[0] = 1: the empty prefix has sum 0, remainder 0. Without this, subarrays starting at index 0 with divisible sum are missed.

Visual Dry Run#

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

Answer: 7

Solution (Optimal)#

from collections import defaultdict
 
def subarraysDivByK(nums: list[int], k: int) -> int:
    cnt = defaultdict(int)
    cnt[0] = 1
    prefix = 0
    ans = 0
 
    for num in nums:
        prefix += num
        r = prefix % k   # Python % always non-negative for positive k
        ans += cnt[r]
        cnt[r] += 1
 
    return ans

var subarraysDivByK = function(nums, k) {
    const cnt = new Map();
    cnt.set(0, 1);
    let prefix = 0, ans = 0;
 
    for (const num of nums) {
        prefix += num;
        // JavaScript % can return negative; normalise to [0, k-1]
        const r = ((prefix % k) + k) % k;
        ans += (cnt.get(r) || 0);
        cnt.set(r, (cnt.get(r) || 0) + 1);
    }
 
    return ans;
};

Time: O(n) — single pass; hash map has at most k entries Space: O(k) — at most k distinct remainders

Common Mistakes#

• Not normalising negative remainders in JS/Java/C++ — (-3) % 5 = -3 in JS; use ((prefix % k) + k) % k
• Not initialising cnt[0] = 1 — misses subarrays starting at index 0 with divisible sum; this is the most common interview bug
• Incrementing cnt[r] before adding it to ans — counts the current position pairing with itself (the empty subarray), giving wrong results
• Using O(n^2) brute force — n = 3 * 10^4 gives 9 * 10^8 operations; TLE
• Confusing with LC 560 — LC 560 tracks exact prefix values; this tracks remainders; the hash map key differs

Interview Tips#

• The two critical rules: initialise cnt[0] = 1, and add cnt[r] to answer before incrementing
• Python's % is always non-negative for positive k — no normalisation needed
• In JavaScript always use ((x % k) + k) % k for negative-safe modulo
• Mention LC 523 as a related problem — same technique but stores the earliest index, not count

Follow-up Questions#

• Return one such subarray: store starting index alongside remainder; when match found, record (stored_index, current_index)
• k = 1: every subarray is valid; answer is n*(n+1)/2; algorithm returns this correctly since every remainder is 0
• Target remainder r instead of 0: look up cnt[(current_remainder - r + k) % k]; rest of algorithm identical
• LC 523 — continuous subarray sum (length >= 2): same technique but store earliest index and check current_index - stored_index >= 2

Key Takeaways#

• Subarray sum divisible by k iff two prefix sums share the same remainder modulo k
• Maintain cnt[r] — frequency of prefix sums with remainder r seen so far
• Always initialise cnt[0] = 1 for the virtual empty prefix before index 0
• Add cnt[r] to answer before incrementing cnt[r] — this ordering is critical for correctness
• Always normalise remainders: ((prefix % k) + k) % k in JS/Java/C++; Python % is already safe
• Time O(n), space O(k) — single-pass technique; the standard FAANG approach for all modular subarray counting problems