What signals in a problem statement indicate the Modulo / divisibility sub-pattern?

"divisible by K"; "sum is a multiple of K"; "remove the smallest subarray so the rest is divisible by p"

What makes Modulo / divisibility different from other sub-patterns?

The lookup key is a remainder, so it's "same remainder" instead of "prefix − K". Watch for negative remainders in C++. Then decide what the map stores from what's asked: - **How many** ranges → count of each remainder (Subarray Sums Divisible by K). - **Does one exist with length ≥ 2** → **first** index of each remainder (Continuous Subarray Sum). - **Shortest** range with a *given* remainder → look up the shifted remainder `cur − need`, keep the **last** index (Make Sum Divisible by P).

Modulo / divisibility (Prefix Sum Sub-pattern)

A range sum is divisible by K exactly when the totals at its two ends leave the same remainder. Store remainders instead of totals.

Signals in the problem statement

›
"divisible by K"
›
"sum is a multiple of K"
›
"remove the smallest subarray so the rest is divisible by p"

What makes it different

The lookup key is a remainder, so it's "same remainder" instead of "prefix − K". Watch for negative remainders in C++. Then decide what the map stores from what's asked:

How many ranges → count of each remainder (Subarray Sums Divisible by K).
Does one exist with length ≥ 2 → first index of each remainder (Continuous Subarray Sum).
Shortest range with a given remainder → look up the shifted remainder cur − need, keep the last index (Make Sum Divisible by P).

Questions

ordered from “learn the idea” to “recognise it without help”

1
Subarray Sums Divisible by K
Basic Anchor·LeetCode #974
WalkthroughMedium
2
Continuous Subarray Sum
Slight Variation·LeetCode #523
WalkthroughMedium
3
Make Sum Divisible by P
Tricky / Edge Case·LeetCode #1590
WalkthroughMedium

Template

modulo-template.cpp

// Count subarrays whose sum is divisible by k.
// Two totals with the same remainder differ by a multiple of k.
long long countDivisible(vector<int>& nums, int k) {
    vector<long long> count(k, 0);  // remainder -> how many prefixes had it
    count[0] = 1;                   // the empty prefix
    long long prefix = 0, result = 0;
    for (int x : nums) {
        prefix += x;
        int rem = ((prefix % k) + k) % k;  // C++ % can be negative; this keeps it in 0..k-1
        result += count[rem];
        count[rem]++;
    }
    return result;
}

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Prefix state / balance Prefix + suffix