Subarrays Divisible by K
Medium · rating 1550 · Prefix Sum, Hashing
The first line has n and k. The second line has n integers. Print the number of contiguous subarrays whose sum is divisible by k.
Constraints: 1 ≤ n ≤ 105, 1 ≤ k ≤ 104
Editorial
Approach
A subarray sum is divisible by k exactly when its two prefix sums share the same remainder mod k. Sweep the prefix remainder and count, for each position, how many earlier prefixes had the same remainder — a hash map of remainder frequencies does this in one pass.
count = {0: 1}; pre = 0; ans = 0
for x in a:
pre = (pre + x) % k
ans += count.get(pre, 0)
count[pre] = count.get(pre, 0) + 1Complexity
Time: O(n). Space: O(k).
Related problems
- Subarrays Summing to K — Hard
- Longest Consecutive Sequence — Medium
- Partition Labels — Medium
- Longest Substring Without Repeats — Medium
- Lamp Toggles — Medium
- Product of Array Except Self — Hard