Subarray Sums Divisible by K
Problem
nums (values may be negative) and an
integer k, count how many non-empty contiguous subarrays have a sum that is
divisible by k.nums = [4,5,0,-2,-3,1], k = 5Output7nums = [5], k = 9Output01 ≤ n ≤ 3·104 · -104 ≤ nums[i] ≤ 104 · 2 ≤ k ≤ 104
Try it yourself
class Solution {
public int subarraysDivByK(int[] nums, int k) {
}
}
k bound a
subarray divisible by k. So for each prefix, the number of good subarrays
ending here equals how many earlier prefixes share its remainder.Instinct Repeated range-sum queries, or "count subarrays whose sum equals / divides K" with negatives allowed? Store running totals and subtract two of them.
Memory hack Any range is two prefixes apart - sum(i..j) = P[j+1] - P[i], so remember every P you've passed.
Open the Prefix Sum guide →Approaches
Brute ForceAll Subarrays with Running Sum
O(n2)Space O(1)For every start index, extend the end while maintaining the running sum and
count each time sum % k == 0. In Java, % of a negative
number is negative or zero, but zero still means divisible, so the test is safe.
public int subarraysDivByK(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum = 0; for (int end = start; end < nums.length; end++) { sum += nums[end]; if (sum % k == 0) count++; } } return count; }
About 4.5·108 steps at the limit — too slow.
OptimalRemainder Frequency Array
O(n + k)Space O(k)Keep freq[r] = number of prefixes seen so far with remainder
r, starting with freq[0] = 1 for the empty prefix. For each
new prefix remainder r, add freq[r] to the answer, then
increment it. Normalise with ((x % k) + k) % k so negatives map into
0..k-1.
public int subarraysDivByK(int[] nums, int k) { int[] freq = new int[k]; freq[0] = 1; // empty prefix int rem = 0, count = 0; for (int x : nums) { rem = ((rem + x) % k + k) % k; // keep remainder in [0, k) count += freq[rem]; // pair with every earlier equal remainder freq[rem]++; } return count; }
Dry runnums = [4,5,0,-2,-3,1], k = 5
- i=04i50-2-31rem=4, +0 → 0
- i=145i0-2-31rem=4, +1 → 1
- i=2450i-2-31rem=4, +2 → 3
- i=3450-2i-31rem=2, +0 → 3
- i=4450-2-3i1rem=4, +3 → 6
- i=5450-2-31irem=0, +1 → 7 ✔
Linear time; remainders are bounded, so a plain array beats a hash map.
freq[r] = c at the end, it contributes
c·(c-1)/2 pairs — a handy way to double-check.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | All Subarrays with Running Sum | O(n2) | O(1) |
| Optimal | Remainder Frequency Array | O(n + k) | O(k) |
- Indexing
freq[sum % k]with a negative sum —ArrayIndexOutOfBoundsException. - Forgetting
freq[0] = 1— misses subarrays starting at index 0. - Incrementing
freq[rem]before adding it — counts the empty subarray.
- Say the identity first: equal prefix remainders ⇔ divisible subarray sum.
- Call out Java's negative modulo explicitly; interviewers look for it.
- Contrast with LC 523: counting needs frequencies, existence-with-length needs indices.