Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Count all sub-arrays having sum divisible by k

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
165 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
All tags
Sort by
Search icon

Interview problems

python

def subArrayCount(arr, k):    count = 0    cumulative_sum = 0    remainder_count = {0: 1}  # To handle the case where cumulative_sum is exactly divisible by k

   for num in arr:        cumulative_sum += num        remainder = cumulative_sum % k

       # Handle negative remainder        if remainder < 0:            remainder += k

       # If this remainder has been seen before, add its count to total        if remainder in remainder_count:            count += remainder_count[remainder]            remainder_count[remainder] += 1        else:            remainder_count[remainder] = 1

   return count

# Example usage if __name__ == "__main__":    arr = [5, 0, 2, 3, 1]    k = 5    print(subArrayCount(arr, k))  # Output: 6  

4 views
0 replies
0 upvotes

Interview problems

C++ Unordered_map Solution

#include <bits/stdc++.h> 

int subArrayCount(vector<int> &arr, int k) {

    unordered_map<int,int> mp;

    int sum = 0;

    int count = 0;

    mp.insert({0,1});

    for(int i = 0;i<arr.size();i++){

        sum = (sum + arr[i]) % k;

        int rem = (sum + k) % k;

        if(mp.find(rem)!=mp.end()){

            count += mp[rem];

            mp[rem] += 1;

        }

        else{

            mp[rem] = 1;

        }

    }

    return count;

}

 

use -ve valued elements containing arrays to understand it efficiently

 

49 views
0 replies
0 upvotes

Interview problems

Python Solution - T.C-O(n)

def subArrayCount(arr, k):

    ans = defaultdict(int)

    ans[0] = 1

    prefix_sum = 0

    count = 0

    for i in range(len(arr)):

        prefix_sum+=arr[i]

        remainder = prefix_sum%k

        count+=ans[remainder]

        ans[remainder]+=1

    return count

 

 

29 views
0 replies
0 upvotes

Interview problems

c++ easy sol

int count=0;

int rem=0;

unordered_map<int,int>mp;

long long sum=0;

mp[0]=1;

for(int i=0;i<arr.size();i++){

sum+=arr[i];

rem=sum%k;

if(rem<0){

rem+=k;

}

if(mp.find(rem)!=mp.end()){

count+=mp[rem];

}

mp[rem]++;

}

return count;

447 views
0 replies
1 upvote

Interview problems

C++ Small O(n) solution

#include <bits/stdc++.h> 
int subArrayCount(vector<int>& nums, int k) {
    unordered_map<int64_t, int> mp{{0, 1}};
    int64_t curSum = 0;
    int ans = 0;
    int n = nums.size();
    for(int i = 0; i < n; ++i){
        curSum += nums[i];
        int64_t temp = curSum % k;
        if(temp < 0) temp += k;
        ans += mp[temp]++;
    }
    return ans;
}
310 views
0 replies
0 upvotes

Interview problems

java solution

import java.util.* ;

import java.io.*; 

import java.util.ArrayList;

 

public class Solution {

 

    public static int subArrayCount(ArrayList < Integer > arr, int k) {

 

         // Write your code here

       

        HashMap<Long,Integer> hmap=new HashMap<>();

        int ans=0;

        long sum=0;

        hmap.put(sum, 1);

        for(int i=0;i<arr.size();i++){

            sum=sum+arr.get(i);

            long rem=sum%k;

            if(rem<0){

               rem+=k;

            }

 

            if(hmap.containsKey(rem)){

                ans=ans+hmap.get(rem);

                hmap.put(rem, hmap.get(rem)+1);

            }

            else{

                hmap.put(rem,1);

            }

        }

        return ans;

    }

    

}

345 views
0 replies
1 upvote

Interview problems

python optimal solution

def subArrayCount(arr, k):
    count = 0 # initialize the count for subarray
    cur_s = 0 # initialize the current sum in the array
    d = {0:1} # {0:1} intialiasing key = 0 and its count as 1
    # take remainder of every current sum divisible by k
    # if remainders are equal of the current sum and one that will come after current sum
    # then the subarray that come in b/w those remainder is divisible by k 
    # this dictionary takes key as remainder and value as no of occurances of that remainder 
    for i in range(len(arr)): 
        cur_s += arr[i] # summation of each element
        r  = cur_s % k # each remainder after division of current sum with k 
        if r in d: # remainder in dictionary
            count += d[r] # count of 0 if more than one remainder encounter
            d[r] += 1 # increment the count for the dictionary as a value
        else: # remainder not in dictionary
            d[r] = 1 
    return count

python

programming

87 views
0 replies
0 upvotes

Interview problems

java code with easy documentation - 3 approaches

# Method - 1

public static int subArrayCount(ArrayList < Integer > arr, int k) { //tc = O(N^2), sc = O() - prefix sum array approach

 

        int prefix[] = new int[arr.size()];

        int count = 0;

        prefix[0] = arr.get(0);

 

        for(int i=1; i<arr.size(); i++){

            prefix[i] = prefix[i-1] + arr.get(i);

        }

       

        for(int start=0; start<arr.size(); start++){

            int sum = 0;

            for(int end=start; end<arr.size(); end++){

                sum = start == 0? prefix[end] : prefix[end] - prefix[start-1];

 

                if(sum%k == 0){

                    count++;

                }

 

            }

        }

       

        return count;

    }

 

# Method - 2 

    public static int subArrayCount2(ArrayList<Integer> arr, int k){//tcc = O(N^2), sc = O(1)

        int count = 0;

        for(int i=0; i<arr.size(); i++){

            int currSum = 0;

            for(int j=i; j<arr.size(); j++){

                currSum += arr.get(j);

 

                if(currSum % k == 0){

                    count++;

                }

 

            }

        }

 

        return count;

    }

 

# Method - 3 // passed all the test cases at leetcode and GFG but didn't pass at Coding ninjas - idk why  ?

    public static int subArrayCount3(ArrayList < Integer > arr, int k) {//tc = O(N), sc = (N)4

        //it's a mathematics related question

        //hint :- count of subarrays will be the frequncy of remainder in hashmap - to know why refer to anu youtube solution because it's

        //not possible here to exxplain in words.

 

        //take hashmap and store remainder and it's frequency.

       

        //explaination - iterate through the arraylist and do sum and get the remainder by dividing sum by k (given) and iterate till

        //you get the same remiander again in this same process and count will be the frequency of that remainder then increase

        //the frequency of that remainder in hashmap.

       

        HashMap<Integer,Integer> mapp = new HashMap<>(); //key - remiander, value - frequency

        mapp.put(0,1); //at first position the sum is zero therefore the remiander will also be zero and it's frequency will also be zero

        int currSum = 0; //initilise the sum with zero

        int count = 0; //count of subarrays

 

        for(int i=0; i<arr.size(); i++){

            currSum += arr.get(i);

            int remainder = currSum%k;

           

            if(remainder < 0){//in case if remiander is negative then add k to that remainder in order to make it positive. why ? refer to any yt video

                remainder += k;

            }

 

            if(mapp.containsKey(remainder)){//if map conatins remainder

                count += mapp.get(remainder); //then add it's frew to count because as we know it it the ans

                mapp.put(remainder,mapp.get(remainder)+1); //and increase the freq of that remainder in hashmap

            }else{

                mapp.put(remainder,1);//if map do not contains remainder then add it to map with freq 1 as it has occured first time

            }

        }

 

        return count;

    }

java

277 views
1 reply
1 upvote

Interview problems

Best C++

/*
#include <bits/stdc++.h> 
int subArrayCount(vector<int> &arr, int k) {
    // Write your code here.
    int ans = 0;

    for(int i = 0 ;i<arr.size() ;i++){
         int sum = 0;
        for(int j = i ;j<arr.size() ;j++){
          sum+=arr[j];

          if(sum%k == 0){
              ans++;
          }
        }  
    }
    return ans ;
}
*/

#include <bits/stdc++.h>
int subArrayCount(vector<int> &arr, int k) { 
    
    // Rem , no.of times that rem occurs
    unordered_map<int,int>remMap;

    remMap[0] = 1;
    int ans = 0;
   long long  int sum = 0;

    for(auto i = 0 ;i<arr.size() ;i++){
        
        sum+=arr[i];

        int rem = (sum % k + k)%k;

        if(remMap.find(rem)!=remMap.end()){
            ans+=remMap[rem];
            remMap[rem]+=1;
        }
        else{
            remMap[rem] = 1;
        }
    }

return ans;



}

// prefix sum method

/*
    
    Time complexity: O(N + K)
    Space complexity: O(K)

    where 'N' is number elements in 'ARR' and 'K' is given second integer.
*/

int subArrayCount(vector<int> &arr, int k) {
    // To store frequency of every remainder.
    vector<int> remArr(k, 0);

    // To store prefix sum.
    long pre = 0;

    for (int i = 0; i < arr.size(); i++) {
        pre += arr[i];
        // If current remainder is 'x' then increase remainder 'x' frequency by '1'.
        remArr[((pre % k) + k) % k] = remArr[((pre % k) + k) % k] + 1;
    }

    int count = 0;  // To store count of the all subarray has sum is divisible by 'k'.

    // Iterate every occurence of remainder.
    for (int i = 0; i < k; i++) {
        if (remArr[i] > 1) {
            // Total subarray with particular remainder.
            int totalPossibleCombination = ((remArr[i] * (remArr[i] - 1)) / 2);
            count = count + totalPossibleCombination;
        }
    }

    // Add remainder '0' frequency.
    count += remArr[0];

    return count;
}










100daysofcode

504 views
0 replies
1 upvote

Interview problems

python easiest solution but with o(n^2) approach

its kind of a  brute force method but it gets the work done 

def subArrayCount(arr, k):

    count = 0

    for i in range(len(arr)):

        current_sum = 0  # Variable to keep track of the sum of the current subarray

        for j in range(i + 1, len(arr) + 1):  # Include the last element in the subarray

            current_sum += arr[j - 1]  # Add the current element to the sum

            if current_sum % k == 0:

                count += 1

    return count

python

74 views
0 replies
0 upvotes
Full screen
Console