74. Divisible Stretches
A delivery company records the net change in package count at each depot along a route; the changes are stored in the array nums and may be negative when more packages leave than arrive. Packages are shipped in crates of size k, so the planners only care about stretches of consecutive depots whose total change is a whole number of crates.
Return the number of non-empty contiguous subarrays of nums whose sum is divisible by k. A sum of zero is divisible by every k, and negative sums are divisible when they are an exact multiple of k. The answer is guaranteed to fit in a 32-bit signed integer.
Example 1
- Input:
- nums = [6,-1,7,3,-9,2], k = 4
- Output:
- 4
- Explanation:
The subarrays [6,-1,7] (sum 12), [-1,7,3,-9] (sum 0), [3,-9,2] (sum -4) and the whole array (sum 8) are divisible by 4.
Example 2
- Input:
- nums = [8,12], k = 4
- Output:
- 3
- Explanation:
All three subarrays [8], [12] and [8,12] have sums 8, 12 and 20, all divisible by 4.
Constraints
1 ≤ nums.length ≤ 106
-109 ≤ nums[i] ≤ 109
1 ≤ k ≤ 106
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n + k)
- Space
- O(k)