Subarray Sum Divisible by k (Prefix Sums + Remainders)

Pattern: Prefix Sum · Difficulty: Medium · Asked at: Meta, Amazon, Yahoo

Classic version: LeetCode 523 · LeetCode 560

Problem

Given non-negative integers nums and a positive integer k, return True if there is a contiguous subarray of length at least 2 whose sum is a multiple of k (0 counts as a multiple).

Examples

has_multiple_run([23, 2, 4, 6, 7], 6)   → True    # [2, 4]
has_multiple_run([23, 2, 6, 4, 7], 13)  → False
has_multiple_run([5, 0, 0, 0], 3)       → True    # [0, 0]

Starter code

def has_multiple_run(nums: list[int], k: int) -> bool:
    pass

Hints

Where this shows up in data engineering

“Equal remainders imply a divisible difference” is the trick behind detecting batches that balance (debits = credits within a period), and the general shape “prefix state + hash map of first occurrence” solves “longest period where X equals Y”, “longest balanced run” and “subarray sum equals k” (see the Python track’s subarray-sum problem).

Solution

def has_multiple_run(nums: list[int], k: int) -> bool:
    first = {0: -1}               # remainder -> first index where the prefix had it
    running = 0
    for i, x in enumerate(nums):
        running = (running + x) % k
        if running in first:
            if i - first[running] >= 2:
                return True
        else:
            first[running] = i    # keep the earliest index: it gives the longest run
    return False

Tests

Your solution should pass these:

assert has_multiple_run([23, 2, 4, 6, 7], 6) is True
assert has_multiple_run([23, 2, 6, 4, 6], 6) is True
assert has_multiple_run([23, 2, 6, 4, 7], 13) is False
assert has_multiple_run([5, 0, 0, 0], 3) is True
assert has_multiple_run([1, 0], 2) is False
assert has_multiple_run([0], 1) is False
assert has_multiple_run([1, 2, 12], 6) is False

Explanation

Key identity: (P[j+1] - P[i]) % k == 0 ⇔ P[j+1] % k == P[i] % k. So we only need to know whether a remainder has been seen before, and where.

Details that trip people up:

• Seed {0: -1} so a prefix that is itself divisible (starting at index 0) is found.
• Store the first occurrence only. Overwriting it would shorten runs and miss the length ≥ 2 requirement ([5, 0, 0, 0]).
• Length ≥ 2 means i - first ≥ 2.

Complexity: O(n) time, O(min(n, k)) space.

Follow-up questions