What is the brute force approach and complexity for Subarray Sums Divisible by K?

Fix each start, grow the end, test sum % k == 0 with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Subarray Sums Divisible by K?

Equal prefix remainders ⇔ divisible subarray; count each remainder with optimal time complexity O(N + K) and space complexity O(K).

How do you identify the pattern for Subarray Sums Divisible by K?

Look for key signals in the prompt: "contiguous subarrays" indicates Ranges [l..r] → a range sum is a difference of two prefix sums.; "count" indicates Count pairs of prefixes, so store how many times each key appeared, not just whether it did.; "divisible by k" indicates The key is the prefix **remainder**, not the prefix value. Equal remainders ⇔ divisible difference.; "may be negative" indicates A window will not work, and C++ `%` can be negative → normalise the remainder..

Subarray Sums Divisible by K

Medium·LeetCode #974Basic Anchor

LeetCode

Jump:

30-Second Mental ModelPrefix Sum (Modulo / divisibility) — count equal remainders

Complexity:O(N²)→O(N + K)

Key Insight

A subarray sum is prefix[r+1] − prefix[l]. It is divisible by k exactly when the two prefixes have the same remainder mod k. So walk once, keep the current remainder, and keep cnt[r] = how many earlier prefixes had remainder r. At each index, add cnt[rem] to the answer.

Core Validity Invariant

nums[l..r] is divisible by k exactly when prefix[l] and prefix[r+1] leave the same remainder mod k.

Problem

You are given an integer array nums (it may contain negative numbers) and a number k.

Count how many contiguous, non-empty subarrays have a sum that is divisible by k (the sum is 0, k, −k, 2k, …).

Input

An integer array nums and an integer k (k ≥ 2).

Output

The number of non-empty subarrays whose sum is a multiple of k.

Example 1

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

Output: 7

The 7 subarrays are [5], [5,0], [0], [-2,-3], [0,-2,-3], [5,0,-2,-3] and the whole array [4,5,0,-2,-3,1] (sum 5).

Example 2

Input: nums = [5], k = 9

Output: 0

The only subarray is [5], and 5 is not a multiple of 9.

Constraints

• 1 ≤ nums.length ≤ 3 · 10^4
• −10^4 ≤ nums[i] ≤ 10^4
• 2 ≤ k ≤ 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Any subarray sum is the difference of two running totals. Which two?
2.
When is the difference of two numbers a multiple of k? Do the numbers need to be equal?
3.
If I only care about divisibility, do I need the full running total, or is a smaller piece of it enough?
4.
How many different values can that smaller piece take? Does that suggest an array instead of a hash map?
5.
What does C++ give for -7 % 5? Is that what I want?

Brute force approach

Idea

For every start, move the end to the right and keep a running sum. Each time the sum is a multiple of k, count one.

Thinking process

1
A subarray is fixed by its start and end, so try every pair.
2
Do not re-add the whole subarray each time: for a fixed start, add one more element as the end moves.
3
Testing sum % k == 0 is safe even for negative sums: in C++ -10 % 5 is 0. The trouble with negatives only starts when we compare two non-zero remainders (see the optimal approach).

Code & Implementation

brute.cpp

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0;

        // Try every start, then grow the end one step at a time.
        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int end = start; end < n; end++) {
                sum += nums[end];
                // A negative sum like -10 still gives -10 % 5 == 0, so this test is safe.
                if (sum % k == 0) count++;
            }
        }
        return count;
    }
};

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length;
        int count = 0;

        // Try every start, then grow the end one step at a time.
        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int end = start; end < n; end++) {
                sum += nums[end];
                // A negative sum like -10 still gives -10 % 5 == 0, so this test is safe.
                if (sum % k == 0) count++;
            }
        }
        return count;
    }
}

class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        n = len(nums)
        count = 0

        # Try every start, then grow the end one step at a time.
        for start in range(n):
            current_sum = 0
            for end in range(start, n):
                current_sum += nums[end]
                # A negative sum like -10 still gives -10 % 5 == 0, so this test is safe.
                if current_sum % k == 0:
                    count += 1
        return count

export function subarraysDivByK(nums: number[], k: number): number {
    const n = nums.length;
    let count = 0;

    // Try every start, then grow the end one step at a time.
    for (let start = 0; start < n; start++) {
        let sum = 0;
        for (let end = start; end < n; end++) {
            sum += nums[end];
            // A negative sum like -10 still gives -10 % 5 == 0, so this test is safe.
            if (sum % k === 0) count++;
        }
    }
    return count;
}

Complexity

Time O(N²)Space O(1)

About n²/2 pairs. With n = 3·10^4 that is around 4.5·10^8 steps — too slow.

Optimized approach

Idea

Start from brute force

Brute force tests every (start, end) pair and checks sum % k == 0 for each one.

Find the repeated work

For a fixed end, it tries every start separately. But whether a start works only depends on one thing: the remainder of the prefix before it. All starts with the same remainder behave the same way, so they can be counted together.

Define the state — what variables do I need?

rem: Remainder of the running total (sum of nums[0..i]) mod k, always kept in 0..k−1.
cnt[r]: How many prefixes seen so far (including the empty one) have remainder r.
count: Number of good subarrays found so far.

Define validity

nums[l..r] is divisible by k exactly when prefix[l] and prefix[r+1] leave the same remainder mod k.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

cnt[0] = 1

The empty prefix has sum 0. Pairing with it means "the subarray starts at index 0".

Each element x

rem = ((rem + x) % k + k) % k

Remainders add like sums, so we never need the full total. The + k and second % k turn C++'s negative remainders (like −1) into the matching one in 0..k−1 (like k − 1).

After updating rem

count += cnt[rem]; then cnt[rem]++

Each earlier prefix with this remainder gives one subarray ending here with a sum divisible by k. Look up before adding the current prefix, or it would pair with itself (an empty subarray).

What does the current window add to the answer?

Index i adds cnt[rem]: one subarray for every earlier prefix with the same remainder. In total, a remainder that appears c times contributes c·(c−1)/2 pairs.

Code & Implementation

optimal.cpp

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        // cnt[r] = how many prefixes so far have remainder r.
        vector<int> cnt(k, 0);
        cnt[0] = 1;               // the empty prefix (sum 0), before index 0

        int rem = 0, count = 0;
        for (int x : nums) {
            // In C++, -3 % 5 is -3, not 2. Adding k and taking % again
            // moves every remainder into 0..k-1.
            rem = ((rem + x) % k + k) % k;
            // Every earlier prefix with the same remainder starts a
            // subarray (ending here) whose sum is a multiple of k.
            count += cnt[rem];
            cnt[rem]++;
        }
        return count;
    }
};

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // cnt[r] = how many prefixes so far have remainder r.
        int[] cnt = new int[k];
        cnt[0] = 1; // the empty prefix (sum 0), before index 0

        int rem = 0, count = 0;
        for (int x : nums) {
            // In Java, -3 % 5 is -3. Adding k and taking % again
            // moves every remainder into 0..k-1.
            rem = ((rem + x) % k + k) % k;
            // Every earlier prefix with the same remainder starts a
            // subarray (ending here) whose sum is a multiple of k.
            count += cnt[rem];
            cnt[rem]++;
        }
        return count;
    }
}

class Solution:
    def subarraysDivByK(self, nums: list[int], k: int) -> int:
        # cnt[r] = how many prefixes so far have remainder r.
        cnt = [0] * k
        cnt[0] = 1

        rem = 0
        count = 0
        for x in nums:
            rem = (rem + x) % k
            count += cnt[rem]
            cnt[rem] += 1
        return count

export function subarraysDivByK(nums: number[], k: number): number {
    // cnt[r] = how many prefixes so far have remainder r.
    const cnt = new Array(k).fill(0);
    cnt[0] = 1;

    let rem = 0;
    let count = 0;
    for (const x of nums) {
        rem = ((rem + x) % k + k) % k;
        count += cnt[rem];
        cnt[rem]++;
    }
    return count;
}

Complexity

Time O(N + K)Space O(K)

One pass over nums, plus O(K) to create the cnt array. With an unordered_map instead it would be O(N) space, but an array is simpler and faster here because k ≤ 10^4.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Fix each start, grow the end, test sum % k == 0	O(N²)	O(1)
Optimal	Equal prefix remainders ⇔ divisible subarray; count each remainder	O(N + K)	O(K)

Why does this belong to this pattern?

Clues in the problem statement

“contiguous subarrays”Ranges [l..r] → a range sum is a difference of two prefix sums.
“count”Count pairs of prefixes, so store how many times each key appeared, not just whether it did.
“divisible by k”The key is the prefix **remainder**, not the prefix value. Equal remainders ⇔ divisible difference.
“may be negative”A window will not work, and C++ `%` can be negative → normalise the remainder.

Contiguous range+count+sum divisible by k+negatives allowed→Prefix Sum (Modulo / divisibility) — count equal remainders

This is the anchor of the Modulo sub-pattern. It is Subarray Sum Equals K with one change: the map key is prefix % k instead of prefix, and the lookup is the same remainder instead of prefix − k. Continuous Subarray Sum keeps the same remainder idea but only asks whether a long-enough pair exists. Make Sum Divisible by P looks for a different remainder (cur − need) and wants the shortest pair.

Don't make this mistake

Using C++ % on a negative running total

✗ rem = (rem + x) % k; // can be negative

✓ rem = ((rem + x) % k + k) % k;

In C++, -1 % 3 is -1, but the prefix −1 belongs with remainder 2 (−1 = 3·(−1) + 2). Prefixes −1 and 2 differ by 3, so they should match, but keys -1 and 2 never do. With a vector it is even worse: cnt[-1] reads outside the array.

Forgetting the empty prefix

✗ vector<int> cnt(k, 0);

✓ vector<int> cnt(k, 0); cnt[0] = 1;

A subarray that starts at index 0 pairs with the empty prefix (sum 0). Without it, [5] with k = 5 gives 0 instead of 1.

Adding the current prefix before looking it up

✗ cnt[rem]++; count += cnt[rem];

✓ count += cnt[rem]; cnt[rem]++;

Counting first would pair the prefix with itself, which is an empty subarray. Every index would add one extra.

Storing sums and looking up prefix − k

✗ count += seen[prefix - k]; seen[prefix]++;

✓ count += cnt[rem]; cnt[rem]++;

This is a pattern-confusion trap. Looking up prefix − k counts subarrays whose sum equals k (Subarray Sum Equals K). Here the sum can be 0, k, 2k, −k, … — any multiple. Store remainders and look up the same remainder.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture