The **Subarray Sums Divisible by K approach** is a technique used to solve problems that involve finding the **number of subarrays in an array whose sum** is divisible by a given number (K). The approach uses the concept of **“prefix sums”** and** “modulo operation” **to efficiently find the number of such subarrays in linear time complexity.

The basic idea is to create a** prefix sum array**, where each element is the** sum of all the elements from the start of the array to that element**. Then, for **each prefix sum, calculate its modulo with K, **and store the result in a** separate array**.

The number of subarrays whose sum is divisible by** K can then be found by counting the number **of occurrences of each modulo result and using that to calculate the number of subarrays that have the same modulo result.

This approach can be implemented using a **hash map (or similar data structure)** to keep track of the count of each modulo result, and iterating through the prefix sum array to update the count of each modulo result as you go.

** The time complexity of this approach is O(n)**, making it more efficient than other **methods that have a time complexity of O(n^2).**

Table of Contents

## Prefix Sum :

```
#include <iostream>
#include <unordered_map>
using namespace std;
int subarraysDivByK(vector<int>& A, int K) {
unordered_map<int, int> mod_count;
mod_count[0] = 1;
int prefix_sum = 0, count = 0;
for (int i = 0; i < A.size(); i++) {
prefix_sum += A[i];
int mod = (prefix_sum % K + K) % K;
if (mod_count.find(mod) != mod_count.end()) {
count += mod_count[mod];
}
mod_count[mod]++;
}
return count;
}
int main() {
vector<int> A = {4, 5, 0, -2, -3, 1};
int K = 5;
cout << subarraysDivByK(A, K) << endl;
return 0;
}
```

```
//code for Leet code C++ :
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> mod_count;
mod_count[0] = 1;
int prefix_sum = 0, count = 0;
for (int i = 0; i < nums.size(); i++) {
prefix_sum += nums[i];
int mod = (prefix_sum % k + k) % k;
if (mod_count.find(mod) != mod_count.end()) {
count += mod_count[mod];
}
mod_count[mod]++;
}
return count;
}
};
```

## Explanation of Prefix Sum :

In this example, the function

takes in two parameters: a vector of integers **subarraysDivByK()**`A`

representing the array and an **integer K **representing the number that the subarray sums should be divisible by. It uses an unordered_map to keep track of the count of each modulo result.

The variable

keeps track of the sum of all the elements from the start of the array to the current element, and **prefix_sum**`count`

keeps track of the number of subarrays whose **sum is divisible by K.**

The function iterates through the array and for each element, it calculates the **prefix_sum** and the **modulo with K**, and stores it in the** mod_count map**. If the mod value already exists in the map, it adds the count of that mod value to the final count. It then increments the count of that mod value in the map. Finally, it returns the count of subarrays whose sum is divisible by K.

It’s worth noting that in c++, the **modulo operation % can** return a **negative number** if the number on the** left is negative**. To avoid this, **we add K **to the result of **prefix_sum % K **to ensure that it will always be a **positive number.**

**Java Solution**:

Here is an example of how the **Subarray Sums Divisible by K approach** can be implemented in **Java** to solve the problem on **LeetCode:**

```
class Solution {
public int subarraysDivByK(int[] A, int K) {
int[] prefixSum = new int[A.length + 1];
for (int i = 1; i <= A.length; i++) {
prefixSum[i] = prefixSum[i - 1] + A[i - 1];
}
int[] modCount = new int[K];
int count = 0;
for (int i = 0; i <= A.length; i++) {
int mod = (prefixSum[i] % K + K) % K;
count += modCount[mod];
modCount[mod]++;
}
return count;
}
}
```

## Explanation:

In this example, the

method takes in two parameters: an integer array **subarraysDivByK()**`A`

representing the array and an integer `K`

representing the number that the subarray sums should be divisible by. It uses two arrays `prefixSum`

and `modCount`

to keep track of the prefix sum and the count of each modulo result respectively.

The variable `count`

keeps track of the number of subarrays whose sum is divisible by K.

The method iterates through the array and for each element, it calculates the** prefixSum **and the modulo with K, and stores it in the** modCount array. I**f the mod value already exists in the array, it adds the count of that mod value to the final count.

It then increments the count of that mod value in the array. Finally, it returns the count of subarrays whose sum is divisible by K.

You can use this implementation to solve the problem on LeetCode, and you should be able to get an O(n) time complexity and O(k) space complexity solution.

## Python:

Here is an example of how the Subarray Sums Divisible by K approach can be implemented in Python to solve the problem:

```
def subarraysDivByK(A, K):
prefix_sum = [0] * (len(A) + 1)
for i in range(1, len(A) + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
mod_count = [0] * K
count = 0
for i in range(len(A) + 1):
mod = (prefix_sum[i] % K + K) % K
count += mod_count[mod]
mod_count[mod] += 1
return count
```

JavaScript:

Here is an example of how the Subarray Sums Divisible by K approach can be implemented in JavaScript to solve the problem:

```
function subarraysDivByK(A, K) {
let prefixSum = new Array(A.length + 1).fill(0);
for (let i = 1; i <= A.length; i++) {
prefixSum[i] = prefixSum[i - 1] + A[i - 1];
}
let modCount = new Array(K).fill(0);
let count = 0;
for (let i = 0; i <= A.length; i++) {
let mod = (prefixSum[i] % K + K) % K;
count += modCount[mod];
modCount[mod]++;
}
return count;
}
```

## Dart

```
int subarraysDivByK(List<int> A, int K) {
var prefixSum = List<int>.generate(A.length + 1, (i) => 0);
for (int i = 1; i <= A.length; i++) {
prefixSum[i] = prefixSum[i - 1] + A[i - 1];
}
var modCount = List<int>.generate(K, (i) => 0);
int count = 0;
for (int i = 0; i <= A.length; i++) {
int mod = (prefixSum[i] % K + K) % K;
count += modCount[mod];
modCount[mod]++;
}
return count;
}
```