Generated by Codex with GPT-5

Quick facts

What the problem is asking

Given an integer array nums and an integer k, count how many contiguous subarrays have a sum divisible by k.

The word “contiguous” is the key constraint. A valid answer must count ranges like nums[left:right + 1], not arbitrary subsets. The same element can participate in many different subarrays, and overlapping ranges are counted separately.

Core idea

The direct approach tries every start and end index, computes each range sum, and checks whether it is divisible by k. Even with a running sum from each start index, that is still O(n^2).

The better approach starts from prefix sums. If prefix[i] is the sum before index i, then the sum of a subarray from left through right is:

prefix[right + 1] - prefix[left]

That subarray is divisible by k when this difference has remainder 0. In modular arithmetic, that happens exactly when:

prefix[right + 1] % k == prefix[left] % k

So the problem becomes much simpler:

while scanning the array, count how many earlier prefix sums had the same remainder as the current prefix sum.

Each earlier matching remainder creates one valid subarray ending at the current index.

How to derive the optimal solution

Start with the fact that two numbers with the same remainder differ by a multiple of k. For example, if two prefix sums both leave remainder 3 when divided by k, subtracting them removes the 3 parts and leaves a clean multiple of k.

That means the algorithm only needs to remember counts of prefix remainders, not the full prefix sums. Initialize remainder 0 with count 1 because a prefix sum that is already divisible by k forms a valid subarray starting at index 0.

For each number:

  1. Add it to the running prefix sum, tracked as a remainder.
  2. Look up how many times this remainder has appeared before.
  3. Add that count to the answer.
  4. Record this remainder for future subarrays.

This is optimal for interview purposes because every element is processed once.

Time complexity is O(n). Space complexity is O(min(n, k)) because there can be at most k distinct remainders, and never more recorded remainders than processed prefixes.

Python solution

from collections import defaultdict
from typing import DefaultDict, List


def count_subarrays_divisible_by_modulus(numbers: List[int], divisor: int) -> int:
    """Return the number of contiguous subarrays whose sum is divisible by divisor."""
    if divisor == 0:
        raise ValueError("divisor must be non-zero")

    modulus = abs(divisor)
    remainder_counts: DefaultDict[int, int] = defaultdict(int)
    remainder_counts[0] = 1

    running_remainder = 0
    divisible_subarray_count = 0

    for number in numbers:
        running_remainder = (running_remainder + number) % modulus

        # Any earlier prefix with the same remainder creates a subarray
        # whose sum is a multiple of the divisor.
        divisible_subarray_count += remainder_counts[running_remainder]
        remainder_counts[running_remainder] += 1

    return divisible_subarray_count


class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        return count_subarrays_divisible_by_modulus(numbers=nums, divisor=k)

Why this works

At each position, the algorithm treats the current prefix as the right boundary of future subarrays.

Suppose the current prefix remainder is r. Any previous prefix with remainder r can be subtracted from the current prefix, and the result will have remainder 0. That difference is exactly the sum of the subarray between those two prefix positions.

The hash map stores how many previous prefixes had each remainder, so every valid subarray ending at the current index is counted in one lookup. Recording the current remainder afterward makes it available to later positions without accidentally counting an empty subarray at the same position.

Common pitfalls

The most common mistake is to store prefix sums instead of prefix remainders. Full sums are unnecessary because divisibility only depends on remainders.

Another common mistake is forgetting the initial remainder_counts[0] = 1. Without it, subarrays starting at index 0 are missed.

Negative numbers are safe in Python because % with a positive divisor returns a non-negative remainder. In languages where modulo can be negative, normalize with something like ((remainder % k) + k) % k.

Interview follow-ups

How would the solution change if the target were sum exactly equal to k?

Use the same prefix-sum idea, but store full prefix sums instead of remainders. A subarray ending at the current index has sum exactly k when an earlier prefix sum equals running_sum - k.

This works because exact equality needs the actual difference, not just divisibility. The complexity stays O(n) time with O(n) extra space, but the map keys are prefix sums rather than values from 0 to k - 1.

How would you return one valid subarray instead of just the count?

Store the first index where each remainder appeared. When the current remainder has been seen before, the subarray after that earlier prefix index through the current index has a sum divisible by k.

This still runs in O(n) time and uses O(min(n, k)) space. The tradeoff is that it returns one example, not the total count. If the interviewer wants the shortest or longest such subarray, store and compare candidate lengths as matches are found.

How would you return all valid subarrays?

Store a list of prefix indices for each remainder. When the current remainder appears, every earlier index in that list forms a valid subarray ending at the current position.

The scanning work is still organized around prefix remainders, but the output can be quadratic because there may be O(n^2) valid subarrays. In that version, O(number_of_answers) output time is unavoidable.

What if k can be negative or zero?

A negative divisor can be handled by using abs(k) because divisibility by k and divisibility by -k are equivalent.

Zero is different because divisibility by zero is undefined. If an interviewer changes the problem to ask for subarrays with sum 0, use the exact prefix-sum counting approach: count how many previous full prefix sums equal the current full prefix sum.

Can this be processed as a stream?

Yes, if the goal is only to keep a running count. Maintain the current remainder, the remainder-count map, and the answer as each new number arrives.

This gives O(1) amortized processing per item and O(min(items_seen, k)) memory. The limitation is that returning actual subarray boundaries from a long stream requires storing prefix indices, which can grow much larger than the compact count-only state.