#974
Medium
Prefix Sum
Subarray Sums Divisible by K
Count subarrays whose sum is divisible by k.
ArrayPrefix Sum
Pattern fit
Two prefixes define a divisible subarray when they have the same remainder modulo k.
Key observation
You are counting equal remainder classes, not exact prefix sums.
Target complexity
O(n) / O(k)
How to break down the solution cleanly
1
Two prefixes define a divisible subarray when they have the same remainder modulo k.
2
You are counting equal remainder classes, not exact prefix sums.
3
Define what the cumulative state means.
4
Build the prefix in one forward pass.
Reference implementation
Python# Generic pattern template
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
range_sum = prefix[r + 1] - prefix[l]
Common pitfalls
warning
Not normalizing negative remainders.
warning
Looking for currentPrefix - k instead of same modulo class.
Common follow-ups
Why do equal remainders imply divisibility?
How is this different from subarray sum equals k?
Continue with related problems
Build repeatable depth inside the Prefix Sum cluster before moving on.