573. Subarray Sums Divisible by K
You are given an integer array nums and a positive integer k. Count the contiguous, non-empty subarrays whose element total is a multiple of k, and return that count as an integer.
A subarray is a run of consecutive elements picked by a start and end position. Two subarrays with identical values but different positions count separately. Note that 0 is a multiple of k, and sums may be negative.
Example 1:
Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7
Explanation: Seven subarrays sum to a multiple of 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], and [-2, -3].
Example 2:
Input: nums = [5], k = 9
Output: 0
Explanation: The only subarray is [5], and 5 is not a multiple of 9.
Constraints:
- 1 ≤ nums.length ≤ 3 * 10⁴
- -10⁴ ≤ nums[i] ≤ 10⁴
- 2 ≤ k ≤ 10⁴
Hints:
The sum of nums[i..j] equals prefix[j+1] - prefix[i], where prefix[t] is the sum of the first t elements. When is that difference divisible by k?
prefix[j+1] - prefix[i] is a multiple of k exactly when the two prefixes leave the same remainder mod k. So count, for each remainder class, how many pairs of prefixes fall into it.
Careful with negatives: in C++ and Java, (-1) % 5 is -1, not 4. Normalize with ((sum % k) + k) % k so every remainder lands in 0..k-1.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Expected output: 7