Count the number of contiguous subarrays whose sum is divisible by a given integer k.
Given an integer array nums and an integer k, count how many contiguous subarrays have a sum that is divisible by k.
A subarray is a non-empty, contiguous segment of the array. A sum is divisible by k when its remainder after division by k is 0.
Your task is to return the total number of such subarrays.
A direct check of every subarray is too slow for large arrays, so you should look for a way to reuse information about cumulative sums and their remainders.
nums: an integer arrayk: a positive integerk.1 <= nums.lengthk > 0nums may contain positive, negative, and zero valuesExample 1
Input
nums = [4,5,0,-2,-3,1], k = 5
Output
7
Explanation
The valid subarrays are counted by comparing prefix-sum remainders. In total, there are 7 contiguous subarrays with sum divisible by 5.
Example 2
Input
nums = [5], k = 9
Output
0
Explanation
The only subarray has sum 5, which is not divisible by 9.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.