33. Count Subarrays Divisible by K
Count continuous ranges whose total sum is an exact multiple of k. A valid range can contain positive values, negative values, or zeros.
Different positions identify different ranges even when their sums agree. Negative remainder behavior differs between languages, so preserve the mathematical divisibility rule.
Example 1
Input
nums=[4,5,0,-2,-3,1], k=5
Output
7
Explanation: Equal normalized prefix remainders count all divisible ranges, including ones containing negative values.
Example 2
Input
nums=[-1,5], k=5
Output
1
Explanation: The two nonempty prefix sums -1 and 4 share normalized remainder four; their difference selects [5].
Constraints
0 <= nums.length <= 105-231 <= nums[i] <= 231 - 11 <= k <= 231 - 1
Hints
Hint 1
Write each subarray sum as a difference of prefix sums.
Hint 2
When is that difference divisible by k?
Hint 3
Count earlier equal normalized remainders, then insert the current one.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Repeated residues contribute multiple new starts
[4,5,0,-2,-3,1]
5
7