Approach Summary
Prefix sum mod k. Two indices with the same running mod form a subarray divisible by k. Track mod frequencies in a HashMap.
How to Recognize This Pattern
- "Subarrays divisible by k"
- Prefix mod: same mod at two indices → divisible subarray between them
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(k)
Tags
Array Hash Table Prefix Sum