#974
Subarray Sums Divisible by K
Medium Prefix remainders
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count the non-empty subarrays whose sum is divisible by k.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count pieces whose sum is a multiple of k.
Why this works: two prefixes with the same remainder mod k differ by a multiple of k. Count remainders as you go.
Example: [4, 5, 0, -2, -3, 1], k = 5
remainders: 4, 4, 4, 2, 4, 0 (start 0)each repeat adds the count seen so fartotal 7
✦Hints open one at a time
A subarray sum is divisible by k when two prefix sums have the same remainder mod k.
Java's % can be negative — normalise with ((sum % k) + k) % k.
↗Approach
Count how many prefixes have each remainder (start with remainder 0 seen once). For each new prefix, add the count of previous prefixes with the same remainder.
</>Solution (Java)
class Solution {
public int subarraysDivByK(int[] nums, int k) {
int[] count = new int[k];
count[0] = 1;
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
int r = ((sum % k) + k) % k; // always 0..k-1
ans += count[r];
count[r]++;
}
return ans;
}
}!Common mistake
Not fixing negative remainders, so -1 and k-1 are counted as different buckets.
Complexity
- Time: O(n).
- Space: O(k).
