Subarray Sums Divisible by K
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Count the non-empty contiguous subarrays whose sum is divisible by k. The array may contain negative numbers.
Examples
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)
