Count All Sub-Arrays Having Sum Divisible By K

Count All Sub-Arrays Having Sum Divisible By K
7 min read
28 December 2022

A lot of programmers are confused about solving the problem based on counting all sub-arrays. If you are one of them, then this guide will be right for you. 

The count all sub-arrays problem is based on knowing sub-arrays numbers that can be formed which will be divisible by a given number. 

For counting the subarray sums divisible by k, the programmers need to understand the problem first and for solving it, you will have to understand what subarray means. 

This tutorial would be your one-go guide to learning everything about the count all sub-arrays problem. 

What are subarray sums divisible by k problem?

You might know about the term “Subarray”, if you don’t, then understand. The Subarrays are the contiguous part of the array. The contiguous part means that there can be different subarrays made but in a linear sequence.

Let’s explain this with an example. 

arr = [ 1, 2, 3, 4, 5, 8]

For the given array, there can be different subarrays like [1,2,3], [1,2,3,4,5], [2,3,4,5], etc. By following the same pattern, we can make a lot of subarrays, however, they should be in linear order and together. 

The Subarray sums divisible by k problem means that we have to find that subarray from the given array which is divisible by the given number k. In this problem, we have to find the subarray by calculating them in every iteration and checking it with the given k number whether it is divisible or not. Once we are done with it, then we have got the subarray. 

However, there is a twist in the problem. When we are finding the subarrays from the given array, then we will have to find the count of the subarrays too. 

Without wasting any more time, let’s begin with the solution.

How To Solve The Sub-arrays having sum divisible by k problem

For finding the count of subarrays sums divisible by k, you will need to know about its correct approach. Without the proper knowledge of the problem statement and approach, you will not be able to solve it. 

First of all, let’s begin with understanding the problem statement. 

Problem Statement

Find the count of sub-arrays having a sum divisible by k. 

[ 0, 2, 3, 5 ]

K= 5

Answer: The count will be 6. All the possible subarrays that you will get are [0], [0, 2, 3], [2, 3], [ 2, 3, 5], [5], [0, 2, 3, 5]. 

Explanation: The count will be increased every time during the iteration, once the number is divisible by k. Now, let’s see its approach and dry run. 

Approach

  • First of all, we will start our iteration from the 0th index. When we are doing it, then we will have to give it certain conditions where we will be checking whether the iterated number is divisible by the given number or not. 
  • When the number is divisible by k, then we will increase the count variable, and if the number is not divisible, then we will keep on iterating. 
  • We will be doing it till the end of the array length. Once the array length ended, then we got the subarrays. 
  • However, when we are doing it, then we have to keep several things in mind. We will only end the iteration, once the starting index is out of length. It is because, when we will start our iteration from the 0th index, then there are possibilities that there will be more subarrays that might be divisible by the k for the same sequence.
  • Therefore, we will end the loop only when the starting index has reached the maximum length. 
  • After it, we will get our correct result and will display the count variable. 

Now, let’s see how the dry run will work for the approach. 

  • We will start our iteration for the problem statement: [ 0, 2, 3, 5 ] with K = 5. 
  • The first iteration will be 0 which is divisible by 5 with 0. 
  • Now, we will increase the count by 1, and the iteration will be started again. 
  • Again, we have got [0,2], but it is not divisible, so we will keep on iterating which will be [0, 2, 3]. We have got 0 + 2 + 3= 5 which is divisible by k. We will again increase the count by 1 and it will be 2. 
  • The iteration will again run and we will get [0, 2, 3, 5] which sums 10 and is divisible by 5. 
  • We will increase the count by 1 and it will be 3. 
  • Again, we will start the iteration, however, this time the starting index will be increased. 
  • Now, we will get the subarrays which will be [2, 3] which is divisible by 5. Thus, we will increase the count by 1 and it will be 4. 
  • Again we will keep on iterating and we will get the elements that will be [2, 3, 5] which sums 10 and is divisible by K. 
  • After it, we will again increase the index. This time we will get 3 elements which are not divisible by k. 
  • Now, on iterating again, we will get [3, 5] which is also not divisible by k. 
  • Thus, we will increase the index as we have reached the maximum ending length. 
  • After increasing the index, we are now on the last length. The element which we have got is 5 and it is divisible by k. 
  • Thus, we will again increase the index, however, this time due to the length having ended, then we will get the answer which is 6.
  • We have counted all subarray with sums divisible by k and we will print the answer.

The only thing that you have to do now is to code the problem. We hope that you have got the working of the approach here. 

Conclusion

Now, you will be able to count the subarrays for the sum divisible by k. The same concept is used for finding the subarray with given XOR . If you have studied binary numbers and bitwise operators, then you might be understanding the problem. 

However, for now, code the count of all subarrays with the sums divisible by k problem. You can use this guide whenever you are having any doubts regarding solving the question.

 

In case you have found a mistake in the text, please send a message to the author by selecting the mistake and pressing Ctrl-Enter.
Comments (0)

    No comments yet

You must be logged in to comment.

Sign In / Sign Up