New update is available. Click here to update.

Posted: 18 Nov, 2020

Difficulty: Moderate

```
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.
```

```
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.
```

```
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.
```

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

```
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
```

```
The O(N^2) solution is trivial, can you solve it in less than O(N^2) time?
```

SIMILAR PROBLEMS

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022

Difficulty: Hard

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Popular Interview Problems: