Given nums and a positive integer k, count the contiguous non-empty subarrays whose sum is divisible by k.
Examples
Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7
Explanation: [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3].
Input: nums = [5], k = 5
Output: 1
Constraints
0 <= len(nums) <= 10**5,1 <= k <= 10**4-10**4 <= nums[i] <= 10**4- Target complexity: O(n) time.
Goals
- Count subarrays via prefix remainders
- Normalise negative remainders