Given an array, you have to find the subarray sum which is divisible by K. 

The Subarray problems are being asked in a lot of coding contests and interviews. For solving the problem, you will require to have the basic concept of the Linear data structure and its working. If you are not good at that, then it will be going to be difficult for you to solve this question.

We are here with the concept of what a subarray is and what things you will have to learn to solve the subarray sums divisible by k problem as it will be very important for your coding journey.

Let’s get inside the blog to find the solution to the Subarray Sum Divisible By K.

 

What are Subarray Sums?

Before landing on the solution, it is very important for you to know about the concept of subarray and the subarray sums. Without knowing about both terms, you will not be able to understand the algorithm of the subarray sums. 

You all must have heard about the term Array. The Array is a type of linear data structure and when we define some continuous elements from the array, then it is known as a Subarray. 

For example, int arr[]= {1,2,3,4}; So, if we take int subarr[]= {2,3,4}, then this will be the subarray because it has some continuous elements of the array. Only those elements will be called subarray, which will be a continuous part of the array. 

The Subarray sum is the addition of all the continuous elements which have been taken out from the array. 

Now, let's move toward the solution of the subarray sums divisible by k. Through the solution, you will also get the concept of solving the problem based on String compression.  

 

How To Solve Subarray Sums Divisible By K

For solving the Subarray sums divisible by K, you need to know about the algorithm that you will be going to follow.

Apart from this, we will do the dry run to check whether our algorithm is correct or not and whether we are going to get the correct solution. 

So, here is the problem statement that you will get on different coding platforms. 

Problem: Given an array, you have to find all the subarray sums which are divisible by the K with the proper approach. 

int arr[]={4, 5, 0, -2, -3, 1}; K= 5; 

 

Algorithm

  • So, first of all, we have to initialize two variables that will store the current sum and the index on which we are traversing. 
  • After storing the sum, we will divide it by the K. 
  • If the number is divisible by K, then we have found the correct subarray and we will increase the subarray index so that we can get to know if there are any more subarrays or not. 
  • If we don’t get the number divisible by the K, then we will increase the starting index of the subarray. 
  • After increasing the index, we will again start with the traversing of the elements and storing the sum. After it, we will check if the stored sum is divisible by K or not. 
  • If the sum is divisible by K, then we will increase the count by one. 
  • Through this, we will be able to get to know about all the subarrays through which the subarrays sum is divisible by K. 

 

Dry Run

Let’s begin with the dry run of the problem which we have taken at the above. 

  • First of all, we will start iterating at the array and will check whether the current sum is divisible by K or not. 
  • An important point is that the current sum and starting index will be zero for the first iteration. Once we have iterated, then we will increase the starting index and reset the current sum with zero. 
  • Now, we will start our first iteration, the current sum will be zero and the index will be zero. 
  • For the first iteration, we will add 0 + 4= 4,4+5=9, 9+0=9, 9+(-2)=7,7+(-3)= 4, 4+1=5. When we are adding the number, then we will keep on checking whether the number is divisible by k or not. If we got that the number is divisible by k, then we will return. 
  • For the first subarray, we have got the current sum which is 5 that is divisible by K. 
  • So, our count will be increased to 1 as we have got our first subarray sum which is divisible by k. 
  • Now, let’s get into the second iteration, the starting index will be 1 and the current sum will be 0. 
  • For the second iteration, 0+5=5, 5+0=5. We have got the subarray which is divisible by k. So, we will increase the count.
  • Now, the third iteration will begin, 0+0=0, 0+(-2)=-2, -2+(-3)=-5, -5+1=-4 which is not divisible by k. 
  • Now, we will increase the starting index. And we will keep on repeating the iteration till we get to the last element. 
  • Once we have reached the last element, then we have got all the counts for the given array. So, we have got our answer through it. 
  • So, if after doing the dry run, you have got these subarrays, then you are going in the right direction: {4,5,0,-2,-3,1}, {5,0},{5,0,-2,-3}. 
  • Some of the subarrays which are not divisible by k are: {0,-2,-3,1}, {-2,-3,1},{-3,1}

Now, you have got the algorithm and the dry run, try to code it in C++ by using proper control statements. 

 

Conclusion

Learning a programming language is not easy if you are not having proper knowledge of the DSA problems. 


Start practicing the DSA problems which are based on String compression, Linked List, etc. to prepare yourself for the coding industry ready.