Update appNew update is available. Click here to update.

Sub-array Sums Divisible By K

Posted: 18 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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. 
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
Follow Up :
The O(N^2) solution is trivial, can you solve it in less than O(N^2) time?