## Introduction

The array is one of the frequently used data structures. An array is a collection of the same type of data components. In an interview, there is a very good chance that you may be asked a question on an array. So, in order to fully grasp the notion of array, we must practice more and more array-related questions. In this blog, we will be discussing a coding problem in which we have to print the total count of all the sub-arrays that have a sum divisible by K.

Must Recommended Topic, __Hash Function in Data Structure____.__

### Problem Statement

Ninja has given you an array of size N. Your task is to count the total number of subarrays having a sum divisible by K.

Note: 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.

### Sample Examples

**Input**

**Output**

`Total Number of even-odd Subarray: 6`

**Explanation**

## Naive Approach

A naive or simple approach would be to generate all the possible subarrays and check while generating whether the subarray has a sum divisible by K or not.

### Algorithm

```
ALGORITHM(ARR, K):
totalCount <- 0
for i <- 0 to arr.size():
for j <- i to arr.size():
If the sum of subarray from i to j is divisible by K:
totalCount <- totalCount + 1
end
end
return totalCount
```

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
int getCount(vector<int> arr, int k){
// For storing the totalCount of subarrays
int totalCount = 0;
// generating subarrays and checking whether there sum is divisible
// by K or not.
for( int i = 0; i < arr.size(); i++){
for( int j = i; j < arr.size(); j++){
// calculating the sum of the subarray
int sum = 0;
for(int k = i; k <= j; k++) sum += arr[k];
// increment totalCount if our sum is divisible by k
if (sum % k == 0) totalCount++;
}
}
// returning the total count of subarrays
return totalCount;
}
// main method
int main(){
// Getting the size of array from user
int n; cout << "Enter the size of the array: ";
cin >> n;
// Getting array elements from user
vector<int> arr(n);
cout << "Enter array elements: ";
for(int i = 0; i < n; i++) cin >> arr[i];
// getting value of K from user
cout << "Enter the value of K: ";
int k; cin >> k;
// getting the count of subarrays and printing it
cout << "Total number of subarray divisible by K: " << getCount(arr, k) << endl;
return 0;
}
```

**Input**

```
Enter the size of the array: 5
Enter 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 taken by the above approach is O(N^3). As we are generating all the possible subarrays and then checking whose sum is divisible by K.

####

**Space Complexity**

No extra space is used. So, the space complexity of the above code is O(1)