Subarray Sum Divisible by K — The Prefix Mod Pattern Mastered

Problem Statement#

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a 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
Explanation: Subarrays with sum divisible by 5:
             [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3]

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

Why This Problem Matters#

Subarray Sum Divisible by K (LC 974) is the canonical example of the prefix mod pattern — one of the most frequently tested interview patterns at Google, Amazon, and Facebook. Understanding this problem deeply means you can instantly solve an entire family of "subarray divisibility" problems without re-deriving the approach.

The problem builds on two classic ideas: prefix sums enable O(1) computation of any subarray sum, and modular arithmetic reduces the infinite range of prefix sums to exactly k distinct remainder classes. Combining them gives an O(n) solution where the naive O(n²) brute force (try every pair of endpoints) would be too slow for n = 3 × 10^4.

Google uses this problem in backend and systems roles because divisibility checks are fundamental in distributed systems: consistent hashing, shard assignments, and load balancing all rely on modular arithmetic. Interviewers watch for candidates who immediately recognise the prefix sum connection and can explain the modular argument cleanly.

The negative number handling is a particular trap. In Python, (-1) % 5 = 4 (always non-negative for positive k). In Java, C++, and JavaScript, (-1) % 5 = -1. Candidates who know this difference and handle it explicitly stand out.

The Core Insight#

Key theorem: Subarray [j+1 ... i] has sum divisible by k if and only if prefix[i] % k == prefix[j] % k.

Proof: sum(j+1..i) = prefix[i] - prefix[j]. For this difference to be divisible by k, we need (prefix[i] - prefix[j]) % k == 0, which means prefix[i] % k == prefix[j] % k.

Algorithm: Maintain freq — a frequency map of how many previous prefix sums had each remainder. Initialise freq[0] = 1 to represent the empty prefix (sum 0, remainder 0). This handles subarrays starting from index 0.

For each element:

1. Update running prefix sum.
2. Compute cur = prefix % k (normalised to be non-negative).
3. Add freq[cur] to the answer (subarrays ending here with divisible sum).
4. Increment freq[cur].

Negative modulo: In languages where a % b can be negative, normalise with ((prefix % k) + k) % k.

Visual Dry Run#

nums = [4, 5, 0, -2, -3, 1], k = 5, freq = {0: 1}

Answer: 7.

Solution (Optimal)#

from collections import defaultdict
 
def subarraysDivByK(nums: list[int], k: int) -> int:
    freq = defaultdict(int)
    freq[0] = 1  # Empty prefix, remainder 0
 
    prefix = 0
    ans = 0
 
    for x in nums:
        prefix = (prefix + x) % k
        # Python's % is always non-negative for positive k
        ans += freq[prefix]
        freq[prefix] += 1
 
    return ans

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

Time: O(n) — single pass through the array. Space: O(k) — frequency map holds at most k distinct remainders.

Common Mistakes#

• Not initialising freq[0] = 1: Without this, subarrays starting from index 0 are missed. The empty prefix has sum 0 and remainder 0.
• Negative modulo in Java/C++/JavaScript: (-3) % 5 = -3 in these languages. Always normalise: ((prefix + x) % k + k) % k.
• Counting pairs instead of prefixes: The count to add is freq[cur] (number of earlier prefixes with the same remainder), not C(freq[cur]+1, 2).
• Not taking mod of the running prefix: Prefix sums can grow to n × max(|nums[i]|) = 3×10^8. Taking mod after each step keeps values small.
• Off-by-one in counting: Update freq[prefix] after counting to avoid pairing an index with itself.

Interview Tips#

• State the theorem first: "Two prefix sums with the same remainder define a subarray with divisible sum."
• Draw the modular equivalence explicitly before writing code.
• Mention the Python vs Java difference in modulo behaviour — interviewers notice when candidates handle this proactively.
• Note that space is O(k), not O(n), because there are only k distinct remainders.

Follow-up Questions#

• How would you solve "count subarrays with sum equal to k" (LC 560)? Same prefix approach but use a map from exact prefix sum to count instead of remainder to count.
• How does this change if you want the longest subarray divisible by k? Store remainder → first occurrence index; answer is max(i - first_occurrence[rem]).
• What if k is very large (up to 10^9)? Still O(n) time; space is O(min(n, k)) since at most n distinct remainders can appear.
• Can you count subarrays with length at least 2 that are divisible by k? The standard approach already counts length-1 subarrays; subtract them if needed.
• What is the connection between this problem and consistent hashing? Consistent hashing assigns keys to servers by hash(key) % num_servers — the same modular classification applied to a stream.

Key Takeaways#

• Subarray sum divisible by k (LC 974) is solved by the prefix mod pattern: two prefix sums with equal remainders define a divisible subarray.
• Initialise freq[0] = 1 to account for the empty prefix; without this, subarrays starting at index 0 are missed.
• Time O(n), space O(k) — only k distinct remainders are possible.
• In Python, % is always non-negative for positive k; in Java/C++/JavaScript, normalise with ((x % k) + k) % k.
• The same pattern extends to "subarray sum equals k" (LC 560), "continuous subarray sum" (LC 523), and "make sum divisible by P" (LC 1590).
• The pattern is also fundamental in distributed systems: shard assignment, consistent hashing, and load balancing all rely on modular classification of keys.
• Google, Amazon, and Facebook test this pattern specifically because divisibility logic appears throughout backend and data engineering systems.