Count Sums Divisible by K
MediumArrays & Hashing
Problem
A packing station fills crates that each hold exactly k items. Consecutive conveyor batches can be combined, and a combination is useful only if its total item count (corrections included, so values can be negative) fills whole crates with nothing left over.
Given an integer array nums and a positive integer k, return the number of non-empty contiguous subarrays whose sum is divisible by k. A sum of 0 counts as divisible.
Example 1
- Input:
- nums = [2, 3, -5, 5, 1], k = 5
- Output:
- 6
[2, 3], [2, 3, -5], [2, 3, -5, 5], [-5], [-5, 5] and [5].
Example 2
- Input:
- nums = [7], k = 3
- Output:
- 0
Constraints
- 1 ≤ nums.length ≤ 3·10^4
- -10^4 ≤ nums[i] ≤ 10^4
- 1 ≤ k ≤ 10^4
Hint
Show the first hint
A subarray sum is a difference of two prefix sums. When is a difference divisible by k?
Walkthrough
How to approach it
01Clarify before coding
- Can values be negative? Yes, so remainders must be normalised into 0..k-1.
- Is a zero sum divisible? Yes.
- Is k always positive? Yes, at least 1.
02Brute force
For every start, extend the end with a running sum and test sum % k == 0.
Cost: O(n²) time: 4.5·10^8 checks for n = 3·10^4, too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.