Subarray Sums Divisible by K
Medium· prefix sum + hash map· modular arithmetic
Problem
Count the non-empty contiguous subarrays whose sum is divisible by k. The array may contain negative numbers.
Examples
Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
For example [5], [5,0], [0] and [4,5,0,-2,-3,1] all have sums divisible by 5.
Input: nums = [7], k = 4
Output: 0
Constraints
- • 1 <= nums.length <= 3 * 10^4
- • -10^4 <= nums[i] <= 10^4
- • 2 <= k <= 10^4
Hints & approach
Hint 1
Two prefix sums with the same remainder bound a divisible subarray.
Hint 2
Count how many prefixes share each remainder.
Hint 3
Negative sums can produce negative remainders in some languages; normalise them.
Approachtry the hints first
Keep a count array of size k for prefix-sum remainders, starting with count[0] = 1. For each element, update the running sum and compute r = ((sum % k) + k) % k so the remainder is never negative. Every earlier prefix with the same remainder forms a divisible subarray ending here, so add count[r] to the answer, then increment count[r].
Time O(n) · Space O(k)