DSA-033 · Normalized remainder multiplicities

Count Subarrays Divisible by K

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 97664 deterministic checks. Learner drafts are not executed.

Understand the problem

Count nonempty contiguous subarrays whose mathematical sum is divisible by a positive modulus k.

nums is non-null with 0–100,000 signed int values, including negatives and zero. k is an int in 1..Integer.MAX_VALUE; both methods throw IllegalArgumentException when k≤0, including for empty input. Preserve nums.
Return a long count. Empty input returns 0 for a valid modulus; the maximum possible count is n(n+1)/2, which can exceed int. Prefix sums use long under the declared size/value bounds.
Normalize each prefix remainder to 0..k-1 using floorMod. Use a hash map of observed remainder frequencies rather than allocating k entries, since k may be much larger than n.

Examples

Input: nums=[4,5,0,-2,-3,1], k=5
Output: 7
Equal normalized prefix remainders count all divisible ranges, including ones containing negative values.
Input: nums=[-1,5], k=5
Output: 1
The two nonempty prefix sums -1 and 4 share normalized remainder four; their difference selects [5].

Before you start

Array positions versus prefix boundaries and half-open intervals
Long arithmetic, frequency maps, and invariant reasoning

Recognize the structure

If two prefix sums have the same residue modulo k, their difference is divisible by k. Unlike an exact-sum lookup, many different prefix values can share one residue, and every earlier occurrence contributes a different starting boundary.

Try before revealing

Hint 1

Write each subarray sum as a difference of prefix sums.

Hint 2

When is that difference divisible by k?

Hint 3

Count earlier equal normalized remainders, then insert the current one.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate sums and test divisibility

For every start, extend a long running sum and test sum%k==0. No normalization is needed when only comparing a single remainder to zero. On [2,-2,0],k=2, every interval is divisible and the baseline counts six. This O(n²), O(1) space method tests actual subarray sums instead of matching prefix states.

Improve the baseline

Reduce the prefix state

Let P[b] be the sum before boundary b. P[right]-P[left] is divisible by k exactly when their normalized remainders agree.

Count prior boundaries

Seed frequency[0]=1 for the empty prefix. For each entered value, update the long prefix, normalize its remainder, and add the number of earlier matching remainders.

Insert after querying

Increase the current remainder’s frequency only after counting earlier boundaries. Otherwise the current boundary pairs with itself and incorrectly contributes an empty interval.

Why it is correct

Residue equivalence

Equal normalized residues mean both prefixes differ from the same representative by multiples of k; subtracting yields a multiple of k. Conversely a divisible difference forces the same residue class.

Frequency invariant

Before querying boundary b, the map counts exactly boundaries 0..b-1 by normalized remainder. Every matching earlier boundary gives one distinct nonempty divisible range ending at b. The zero seed includes ranges beginning at the first element.

Complete counting

Query-before-insert excludes empty ranges. Every nonempty range has one end boundary, so no valid range is missed or counted twice. The scan and bounded validation terminate; long stores both wide prefixes and the potentially quadratic count.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.HashMap;
import java.util.Map;
public final class Solution {
    public static long subarraysDivByK(int[] nums, int k) {
        if (k <= 0) throw new IllegalArgumentException("k must be positive");
        Map<Integer, Long> frequency = new HashMap<>();
        frequency.put(0, 1L);
        long prefix = 0, count = 0;
        for (int value : nums) {
            prefix += value;
            int remainder = (int) Math.floorMod(prefix, (long) k);
            long earlier = frequency.getOrDefault(remainder, 0L);
            count += earlier;
            frequency.put(remainder, earlier + 1);
        }
        return count;
    }
    public static long baseline(int[] nums, int k) {
        if (k <= 0) throw new IllegalArgumentException("k must be positive");
        long count = 0;
        for (int start = 0; start < nums.length; start++) {
            long sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum % k == 0) count++;
            }
        }
        return count;
    }
}

Read the meaningful blocks

floorMod on long

Java % can produce negative residues. Math.floorMod(prefix,(long)k) gives the unique representative in [0,k), then casting to int is safe.

Long frequencies and answer

Even one repeated residue can create over five billion intervals at n=100000. A set loses multiplicity and an int count can overflow.

Observed-key map

At most min(n+1,k) residues occur. Allocating an int[k] array for Integer.MAX_VALUE is unnecessary and can exhaust memory.

Complexity

Expected O(n) time with hash-map operations and O(min(n+1,k)) auxiliary keys. Prefix and frequency arithmetic remain within long under the contract.

The baseline uses O(n²) time and O(1) space. A k-slot array variant takes O(n+k) time including initialization and O(k) storage; use it only when k is suitably bounded.

Exact-state walkthroughs

Reveal normal and boundary traces

Repeated residues contribute multiple new starts

Input: {"nums":[4,5,0,-2,-3,1],"k":5} · Result: 7

Step 1 of 14: Seed the empty prefix once.

The map initially contains only boundary zero, before any nonempty range exists.

Original input — processed prefix

0: 4
1: 5
2: 0
3: -2
4: -3
5: 1

Normalized remainder → boundary count

0 → 1

State after this step
Variable	Value
values	`[4,5,0,-2,-3,1]`
boundary	`0`
prefix	`0`
count	`0`
remainderFrequencies	`[[0,1]]`

See the affected Java block

 1 import java.util.HashMap;
 2 import java.util.Map;
 3 public final class Solution {
 4     public static long subarraysDivByK(int[] nums, int k) {
 5         if (k <= 0) throw new IllegalArgumentException("k must be positive");
 6         Map<Integer, Long> frequency = new HashMap<>();
 7         frequency.put(0, 1L);
 8         long prefix = 0, count = 0;
 9         for (int value : nums) {
10             prefix += value;
11             int remainder = (int) Math.floorMod(prefix, (long) k);
12             long earlier = frequency.getOrDefault(remainder, 0L);
13             count += earlier;
14             frequency.put(remainder, earlier + 1);
15         }
16         return count;
17     }
18     public static long baseline(int[] nums, int k) {
19         if (k <= 0) throw new IllegalArgumentException("k must be positive");
20         long count = 0;
21         for (int start = 0; start < nums.length; start++) {
22             long sum = 0;
23             for (int end = start; end < nums.length; end++) {
24                 sum += nums[end];
25                 if (sum % k == 0) count++;
26             }
27         }
28         return count;
29     }
30 }
31

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the empty prefix once.
The map initially contains only boundary zero, before any nonempty range exists.
values
[4,5,0,-2,-3,1]
boundary
0
prefix
0
count
0
remainderFrequencies
[[0,1]]
Count earlier boundaries in the same normalized residue class.
The current boundary has not been inserted, so every counted range is nonempty. Negative prefix values use normalized residues.
values
[4,5,0,-2,-3,1]
boundary
1
prefix
4
count
0
remainderFrequencies
[[0,1]]
i
0
remainder
4
earlier
0
phase
"query"
Insert this boundary only after counting.
Frequencies now describe all boundaries through the current one for the next iteration.
values
[4,5,0,-2,-3,1]
boundary
1
prefix
4
count
0
remainderFrequencies
[[0,1],[4,1]]
i
0
remainder
4
earlier
0
phase
"insert"
Count earlier boundaries in the same normalized residue class.
The current boundary has not been inserted, so every counted range is nonempty. Negative prefix values use normalized residues.
values
[4,5,0,-2,-3,1]
boundary
2
prefix
9
count
1
remainderFrequencies
[[0,1],[4,1]]
i
1
remainder
4
earlier
1
phase
"query"
Insert this boundary only after counting.
Frequencies now describe all boundaries through the current one for the next iteration.
values
[4,5,0,-2,-3,1]
boundary
2
prefix
9
count
1
remainderFrequencies
[[0,1],[4,2]]
i
1
remainder
4
earlier
1
phase
"insert"
Count earlier boundaries in the same normalized residue class.
The current boundary has not been inserted, so every counted range is nonempty. Negative prefix values use normalized residues.
values
[4,5,0,-2,-3,1]
boundary
3
prefix
9
count
3
remainderFrequencies
[[0,1],[4,2]]
i
2
remainder
4
earlier
2
phase
"query"
Insert this boundary only after counting.
Frequencies now describe all boundaries through the current one for the next iteration.
values
[4,5,0,-2,-3,1]
boundary
3
prefix
9
count
3
remainderFrequencies
[[0,1],[4,3]]
i
2
remainder
4
earlier
2
phase
"insert"
Count earlier boundaries in the same normalized residue class.
The current boundary has not been inserted, so every counted range is nonempty. Negative prefix values use normalized residues.
values
[4,5,0,-2,-3,1]
boundary
4
prefix
7
count
3
remainderFrequencies
[[0,1],[4,3]]
i
3
remainder
2
earlier
0
phase
"query"
Insert this boundary only after counting.
Frequencies now describe all boundaries through the current one for the next iteration.
values
[4,5,0,-2,-3,1]
boundary
4
prefix
7
count
3
remainderFrequencies
[[0,1],[4,3],[2,1]]
i
3
remainder
2
earlier
0
phase
"insert"
Count earlier boundaries in the same normalized residue class.
The current boundary has not been inserted, so every counted range is nonempty. Negative prefix values use normalized residues.
values
[4,5,0,-2,-3,1]
boundary
5
prefix
4
count
6
remainderFrequencies
[[0,1],[4,3],[2,1]]
i
4
remainder
4
earlier
3
phase
"query"
Insert this boundary only after counting.
Frequencies now describe all boundaries through the current one for the next iteration.
values
[4,5,0,-2,-3,1]
boundary
5
prefix
4
count
6
remainderFrequencies
[[0,1],[4,4],[2,1]]
i
4
remainder
4
earlier
3
phase
"insert"
Count earlier boundaries in the same normalized residue class.
The current boundary has not been inserted, so every counted range is nonempty. Negative prefix values use normalized residues.
values
[4,5,0,-2,-3,1]
boundary
6
prefix
5
count
7
remainderFrequencies
[[0,1],[4,4],[2,1]]
i
5
remainder
0
earlier
1
phase
"query"
Insert this boundary only after counting.
Frequencies now describe all boundaries through the current one for the next iteration.
values
[4,5,0,-2,-3,1]
boundary
6
prefix
5
count
7
remainderFrequencies
[[0,2],[4,4],[2,1]]
i
5
remainder
0
earlier
1
phase
"insert"
Return the contract result.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
result
7

Negative and positive prefixes share one residue

Input: {"nums":[-1,5],"k":5} · Result: 1

Step 1 of 6: Seed the empty prefix once.

The map initially contains only boundary zero, before any nonempty range exists.

Original input — processed prefix

0: -1
1: 5

Normalized remainder → boundary count

0 → 1

State after this step
Variable	Value
values	`[-1,5]`
boundary	`0`
prefix	`0`
count	`0`
remainderFrequencies	`[[0,1]]`

See the affected Java block

 1 import java.util.HashMap;
 2 import java.util.Map;
 3 public final class Solution {
 4     public static long subarraysDivByK(int[] nums, int k) {
 5         if (k <= 0) throw new IllegalArgumentException("k must be positive");
 6         Map<Integer, Long> frequency = new HashMap<>();
 7         frequency.put(0, 1L);
 8         long prefix = 0, count = 0;
 9         for (int value : nums) {
10             prefix += value;
11             int remainder = (int) Math.floorMod(prefix, (long) k);
12             long earlier = frequency.getOrDefault(remainder, 0L);
13             count += earlier;
14             frequency.put(remainder, earlier + 1);
15         }
16         return count;
17     }
18     public static long baseline(int[] nums, int k) {
19         if (k <= 0) throw new IllegalArgumentException("k must be positive");
20         long count = 0;
21         for (int start = 0; start < nums.length; start++) {
22             long sum = 0;
23             for (int end = start; end < nums.length; end++) {
24                 sum += nums[end];
25                 if (sum % k == 0) count++;
26             }
27         }
28         return count;
29     }
30 }
31

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the empty prefix once.
The map initially contains only boundary zero, before any nonempty range exists.
values
[-1,5]
boundary
0
prefix
0
count
0
remainderFrequencies
[[0,1]]
Count earlier boundaries in the same normalized residue class.
The current boundary has not been inserted, so every counted range is nonempty. Negative prefix values use normalized residues.
values
[-1,5]
boundary
1
prefix
-1
count
0
remainderFrequencies
[[0,1]]
i
0
remainder
4
earlier
0
phase
"query"
Insert this boundary only after counting.
Frequencies now describe all boundaries through the current one for the next iteration.
values
[-1,5]
boundary
1
prefix
-1
count
0
remainderFrequencies
[[0,1],[4,1]]
i
0
remainder
4
earlier
0
phase
"insert"
Count earlier boundaries in the same normalized residue class.
The current boundary has not been inserted, so every counted range is nonempty. Negative prefix values use normalized residues.
values
[-1,5]
boundary
2
prefix
4
count
1
remainderFrequencies
[[0,1],[4,1]]
i
1
remainder
4
earlier
1
phase
"query"
Insert this boundary only after counting.
Frequencies now describe all boundaries through the current one for the next iteration.
values
[-1,5]
boundary
2
prefix
4
count
1
remainderFrequencies
[[0,1],[4,2]]
i
1
remainder
4
earlier
1
phase
"insert"
Return the contract result.
The result follows the declared boundaries, multiplicities, strictness, and numeric contract.
result
1

Test the contract

Input: nums=[], k=3
Output: 0
No nonempty ranges.
Input: nums=[0,0], k=7
Output: 3
Repeated residue multiplicities.
Input: nums=[3,-2,9], k=1
Output: 6
Every integer sum is divisible by one.
Input: nums=[], k=0
Output: IllegalArgumentException
Invalid modulus is rejected before scanning.

Common mistakes and counterexamples

Compare unnormalized Java remainders

Counterexample: For [-1,5],k=5, raw prefix remainders -1 and 4 differ despite representing the same class.

Normalize both to 0..k-1.

Insert the current prefix first

Counterexample: With [1],k=2, self-pairing would falsely count one empty range.

Query earlier frequencies before insertion.

Use a set or only the earliest boundary

Counterexample: [0,0],k=7 has three divisible ranges.

Keep multiplicities for counting; earliest positions solve a different longest-length objective.

Follow-ups

Find the longest divisible range.

Replace frequencies with earliest boundaries for each normalized residue. A repeated residue gives a distance; preserve the earliest occurrence rather than overwriting it.

Count a chosen remainder r.

For a normalized target r, find earlier residue floorMod(currentResidue-r,k). Normalize the subtraction in long and keep the query-before-insert ordering.

Compare exact-sum and modulo counting.

Exact-sum counting looks up currentPrefix-target, retaining full prefix values. Divisibility deliberately merges infinitely many sums into one residue class. Their map states are related but not interchangeable.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 138/20,000 characters

Self-review

I normalize negative prefix remainders.I seed zero once and query before inserting.I choose frequencies for count and earliest boundaries for length.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Prefix sums: boundaries and multiplicity

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.