Sub-array Sums Divisible By K

Moderate

0/80

Average time to solve is 25m

Contributed by

5 upvotes

Problem statement

Given an array of integers of size ‘N’ and a positive integer ‘K’. Return the number of non-empty subarrays whose sum is divisible by K.

A subarray is a contiguous subset of an array.

For Example :

Consider an array of size four. The elements of the array are { -4, 5, 6, 1}. 
The value of K is 4. 
The subarrays whose sum is divisible by 4 are as  follows:
[ -4 ] 
[-4, 5, 6, 1] 
[ 5, 6, 1] 
Hence, there are three subarrays whose sum is divisible by 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains an integer T, the number of test cases.

The first line of every test case contains two space-separated integers ‘N’ and ‘K‘ denoting the size of the array and the positive integer K. 

The second line of every test case contains ‘N’ space-separated integers.

Output Format :

For every test case, print the count of the subarrays whose sum is divisible by K. 

The output of each test case is printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10    
1 <= N <= 10^5
1 <= K <= 10^3
-10^3 <= data <= 10^3

Where ‘data’ denotes the value of the elements of the array.

Time Limit: 1 sec

Sample Input 1 :

2 
5 5 
5 -5 0 -1 2  
1 4
3

Sample Output 1 :

6
0

Explanation of Sample Input 1 :

Test Case 1: Among all the possible subarrays of the given array, there are six subarrays whose sum is divisible by 5. 
[ 5 ] 
[ 5, -5]
[ 5, -5, 0 ]
[ -5, 0 ]
[ -5 ]
[ 0 ] 

Test Case 2: The only subarray [3] is not divisible by 4.

Sample Input 2 :

2
6 5
4 5 0 -2 -3 1
7 3
6 7 1 -2 3 4 9

Sample Output 2 :

7
9

Console