38

# Count all sub-arrays having sum divisible by k

Difficulty: MEDIUM
Contributed By
Ambuj verma
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

#### Given an array βARRβ and an integer βKβ, your task is to find all the count of all sub-arrays whose sum is divisible by the given integer βKβ.

##### Note:
``````If there exists no subarray in the given sequence whose sum is divisible by βKβ then simply return β0β.
``````
##### Example:
``````Suppose the given array is βARRβ = { 5, 0, 2, 3, 1} and βK = 5β.
As we can see in below image, there are a total of 6 subarrays that have the total sum divisible by βKβ
So we return the integer 6.
``````

##### Input format:
``````The first line of input contains an integer βTβ denoting the number of test cases.
The next β2*Tβ lines represent the βTβ test cases.

The first line of each test case contains two space-separated integers the first integer βNβ will denote the number of elements in the array and the second integer denotes integer βKβ.

The second line of each test case contains βNβ space-separated integer that is elements of the array.
``````
##### Output Format
``````For each test case, print an integer that is the count of all subarray that sum is divisible by βKβ.
``````
##### Note:
``````You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= T <= 50
1 <= K,N <= 10^4
-10^9 <= ARR[i] <= 10^9

Time limit: 1 second
``````
##### Sample Input 1:
``````2
3 2
2 3 1
4 1
1 2 3 4
``````
##### Sample Output 1:
``````3
10
``````
##### Explanation of sample input 1:
``````Test Case 1:

Given βARRβ is { 2, 3,1 } and βKβ is β2β.
All the sub-array with sum is divided by βKβ are -
{ 2 }  because the sum is 2 and sum 2 is divisible by 2
{ 3, 1 } because the sum is 3 + 1 = 4 and sum 4 is divisible by 2.
{ 2, 3, 1 } because the sum is 2 + 3 + 1 = 6 and sum 6 is divisible by 2.

Hence there is a total of three subarrays that has sum divisible by 2.

Test Case 2:

Given βARRβ is { 1, 2, 3, 4 } and βKβ is β1β.
Given βKβ is 1 thatβs why each and every sub-arrays sum will be divisible by β1β and with the size of β4β array total number of subarray possible is β( 4*5 /2 ) = 20/2 = 10β.
All possible subarray -
{ 1 }, { 2 }, { 3 }, { 4 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 1, 2, 3 }, { 2, 3, 4 }, { 1, 2, 3, 4 } and all subarray sum is divisible by β1β.
Hence there are overall 10 subarrays that has sum divisible by β1β.
``````
##### Sample Input 2:
``````2
4 3
1 4 5 2
3 2
1 1 2
``````
##### Sample Output 2:
``````2
3
``````
Console