Count all Subarrays having Sum Divisible by K

Optimal Approach

As we have seen, the time taken by the above approach is O(N^2) which is not that good. To solve this problem more optimally we can use hashmaps and heaps. Using a hashmap we can store the frequency of every remainder and we can use this information to solve our problem. 

Have a look at the algorithm and the implementation below to get a clear idea about how we can use hashmap.

Algorithm

1. Start 
2. Create a hashmap to store the frequency of remainders.
3. Create 3 variables to store count, sum, and remainder.
4. Initialize frequency of 0 to 1 in our hashmap.
5. Loop over the whole array and do the following:
   1. Increment sum by the array element
   2. Get the remainder
   3. If the remainder is already present inside our hashmap then increment the total count by frequency of remainder.
   4. Else initialize the frequency of remainder inside our hashmap to 1.
6. Print total count.
7. Exit.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

int getCount(vector<int> arr, int k){
    // storing total number of subarrays
    int totalCount = 0;

    // hash map
    unordered_map<int, int> map;
    
    // increasing the count of 0 by 1 in our hashmap
    map[0] = 1;

    long sum = 0;
    int rem = 0;

    // iterating through whole array
    for(int i = 0; i < arr.size(); i++){

        // adding the array element into our sum
        sum += arr[i];

        // getting remainder
        rem = (sum % k + k) % k;

        // if the value of remainder inside our hashmap is not zero
        // increment the totalCount by rem
        // and increment the value of remainder inside our hashmap by 1
        // else initialize the remainder inside our hashmap to 1
        if(map[rem] != 0){
            totalCount += map[rem];
            map[rem]++;
        }
        else {
            map[rem] = 1;
        }
    }

    // returning the total count
    return totalCount;
}


int main(){
    // getting size of array from user
    int n; 
    cout << "Enter the size of the array: ";
    cin >> n;

    cout << "Enter the array elements: ";

    // getting array elements from user
    vector<int> arr(n);
    for(int i = 0; i < n; i++) cin >> arr[i];

    // getting the value of K
    int k;
    cout << "Enter the value of K: ";
    cin >> k;

    // calling our algorithm and printing the result on screen
    cout << "Total number of subarray divisible by K: " << getCount(arr, k) << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

Enter the size of the array: 5
Enter the array elements: 5 0 2 3 1
Enter the value of K: 5

Output

Total number of subarray divisible by K: 6

Time Complexity

The time complexity of the above program is O(n), as we are iterating the array only once.
 

Space Complexity

A hashmap is used to count the frequency. So, the space complexity of the above approach is O(n).

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

Is Subarray contiguous?

Yes, A subarray is a part of an array that is contiguous. For example, if the array is {3, 1, 6} then {1, 6} can be one of the many subarrays of the original array.
 

What are linear data structures?

A linear data structure connects data items so that they are ordered sequentially, and each element is connected to the element in front of it and behind it.
 

What are the 4 types of linear data structure?

Array, Queue, Stack, and Linked List are the four types of linear data structures.

Conclusion

In this article, we have extensively discussed a coding problem in which we have to count the total number of subarrays whose sum is divisible by K. We have discussed two different approaches to solve the problem.

You can have a look at our Youtube tutorial to get more information regarding the above question.

We hope that this blog has helped you enhance your knowledge about the above question and if you would like to learn more. Check out more of our blogs related to coding questions Smallest subarray with sum greater than a given value, Maximize the Sum of Max and Min of K Subarrays, Sum of All Elements With Odd Frequency in the Given Subarray,  and many more on our Website.

Recommended problems -

• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k

You can also check Interview Preparation Resources and Interview Experiences if you are interested in cracking the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc.

Upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and more with our Coding Ninjas Studio Guided Path.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!