Count all sub-arrays having sum divisible by k

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
166 upvotes
Asked in companies
MicrosoftSnapdealProtium

Problem statement

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.

subsequence

Detailed explanation ( Input/output format, Notes, Images )
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
Hint

Try calculating the sum of all the sub-arrays possible.

Approaches (3)
Brute Force (Time Limit Exceed)

The basic idea is that try each and every possible subarray and find the sum of the current subarray and check if the current sum is divisible by ‘K’. 

 

  • To implement this approach we use two nested loops and one ‘COUNT’ variable to store all subarray with sum divisible by ‘K’ and initially ‘COUNT’ is ‘0’.
  • Iterate outer loop ‘i’ from ‘0’ to ‘N-1’ for every position of ‘ARR’.
  • Add check current sum is divisible by ‘K’
    • If divisible then increase ‘COUNT’ by ‘1’.
  • Iterate an inner loop ‘j’ from ‘i’ to ‘N-1’ and ‘j’ will represent a subarray from ‘i' to ‘j’
    • Store sum of subarray from ‘i’ to ‘j’ in a ‘CUR_SUM’ variable.
    • Add ‘ARR[j]’ in ‘CUR_SUM’.
    • Check every point is ‘CUR_SUM’ is divisible by ‘K’ or not
      • If ‘CUR_SUM % K == 0 ’ then increase the value of ‘COUNT’ by ‘1’.
  • Iterate for the next value of ‘i’.
  • In the end, return ‘COUNT’.
Time Complexity

O(N ^ 2), where ‘N' is a number of elements in ‘ARR’.

 

We are using two nested loops of size ‘N’.

Space Complexity

O(1).

 

We are using constant space.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Count all sub-arrays having sum divisible by k
Full screen
Console