372. Sridharan and the Shopkeeper
0
Medium
Sridharan, a chocolate enthusiast, visited a shop that had an array of integers representing the number of chocolates at each index. Sridharan wants to obtain multiple of K chocolates. The shopkeeper has agreed to provide all subarrays whose sum of chocolates is divisible by K. Determine the total number of ways Sridharan can obtain chocolates, i.e., the number of non-empty subarrays with a sum divisible by K.
Input Format
The first line of input contains two integers N (size of the array) and K. The second line contains N integers representing the number of chocolates at each index in the array.
Output Format
Print the total number of ways Sridharan can obtain chocolates.
Note: If arr[i] is negative, it means Sridharan has to give arr[i] chocolates to the shopkeeper.
Example
Input
6 5
4 5 0 -2 -3 1
Output
7
Constraints
1<=N<=10^5
-10^5<=arr[i]<=10^5
2<=k<=10^4
-10^5<=arr[i]<=10^5
2<=k<=10^4
Loading...
View Submissions
Console