# Count all sub-arrays having sum divisible by k

You are given an array of positive and/or negative integers and a value K . The task is to find count of all sub-arrays whose sum is divisible by K?**Examples :**

Input : arr[] = {4, 5, 0, -2, -3, 1}, K = 5 Output : 7 // there are 7 sub-arrays whose sum is divisible by K // {4, 5, 0, -2, -3, 1} // {5} // {5, 0} // {5, 0, -2, -3} // {0} // {0, -2, -3} // {-2, -3}

Become a success story instead of just reading about them. Prepare for coding interviews at Amazon and other top product-based companies with our **Amazon Test Series**. Includes **topic-wise practice questions on all important DSA topics** along with **10 practice contests** of 2 hours each. Designed by industry experts that will surely help you practice and sharpen your programming skills. Wait no more, start your preparation today!

A **simple solution** for this problem is to one by one calculate sum of all sub-arrays possible and check divisible by K. The time complexity for this approach will be O(n^2).

An **efficient solution** is based on below observation.

Let there be a subarray (i, j) whose sum is divisible by k sum(i, j) = sum(0, j) - sum(0, i-1) Sum for any subarray can be written as q*k + rem where q is a quotient and rem is remainder Thus, sum(i, j) = (q1 * k + rem1) - (q2 * k + rem2) sum(i, j) = (q1 - q2)k + rem1-rem2 We see, for sum(i, j) i.e. for sum of any subarray to be divisible by k, the RHS should also be divisible by k. (q1 - q2)k is obviously divisible by k, for (rem1-rem2) to follow the same, rem1 = rem2 where rem1 = Sum of subarray (0, j) % k rem2 = Sum of subarray (0, i-1) % k

So if any sub-array sum from index i’th to j’th is divisible by k then we can say**a[0]+…a[i-1] (mod k) = a[0]+…+a[j] (mod k)**

The above explanation is provided by Ekta Goel.

So we need to find such a pair of indices (i, j) that they satisfy the above condition. Here is the algorithm :

- Make an auxiliary array of size k as
**Mod[k]**. This array holds the count of each remainder we are getting after dividing cumulative sum till any index in arr[]. - Now start calculating cumulative sum and simultaneously take it’s mod with K, whichever remainder we get increment count by 1 for remainder as index in Mod[] auxiliary array. Sub-array by each pair of positions with same value of ( cumSum % k) constitute a continuous range whose sum is divisible by K.
- Now traverse Mod[] auxiliary array, for any Mod[i] > 1 we can choose any two pair of indices for sub-array by
**(Mod[i]*(Mod[i] – 1))/2**number of ways . Do the same for all remainders < k and sum up the result that will be the number all possible sub-arrays divisible by K.

## C++

`// C++ program to find count of subarrays with` `// sum divisible by k.` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Handles all the cases` `// function to find all sub-arrays divisible by k` `// modified to handle negative numbers as well` `int` `subCount(` `int` `arr[], ` `int` `n, ` `int` `k)` `{` ` ` `// create auxiliary hash array to count frequency` ` ` `// of remainders` ` ` `int` `mod[k];` ` ` `memset` `(mod, 0, ` `sizeof` `(mod));` ` ` `// Traverse original array and compute cumulative` ` ` `// sum take remainder of this current cumulative` ` ` `// sum and increase count by 1 for this remainder` ` ` `// in mod[] array` ` ` `int` `cumSum = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `cumSum += arr[i];` ` ` `// as the sum can be negative, taking modulo twice` ` ` `mod[((cumSum % k) + k) % k]++;` ` ` `}` ` ` `int` `result = 0; ` `// Initialize result` ` ` `// Traverse mod[]` ` ` `for` `(` `int` `i = 0; i < k; i++)` ` ` `// If there are more than one prefix subarrays` ` ` `// with a particular mod value.` ` ` `if` `(mod[i] > 1)` ` ` `result += (mod[i] * (mod[i] - 1)) / 2;` ` ` `// add the elements which are divisible by k itself` ` ` `// i.e., the elements whose sum = 0` ` ` `result += mod[0];` ` ` `return` `result;` `}` `// Driver program to run the case` `int` `main()` `{` ` ` `int` `arr[] = { 4, 5, 0, -2, -3, 1 };` ` ` `int` `k = 5;` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `cout << subCount(arr, n, k) << endl;` ` ` `int` `arr1[] = { 4, 5, 0, -12, -23, 1 };` ` ` `int` `k1 = 5;` ` ` `int` `n1 = ` `sizeof` `(arr1) / ` `sizeof` `(arr1[0]);` ` ` `cout << subCount(arr1, n1, k1) << endl;` ` ` `return` `0;` `}` `// This code is corrected by Ashutosh Kumar` |

## Java

`// Java program to find count of` `// subarrays with sum divisible by k.` `import` `java.util.*;` `class` `GFG {` ` ` `// Handles all the cases` ` ` `// function to find all sub-arrays divisible by k` ` ` `// modified to handle negative numbers as well` ` ` `static` `int` `subCount(` `int` `arr[], ` `int` `n, ` `int` `k)` ` ` `{` ` ` `// create auxiliary hash array to` ` ` `// count frequency of remainders` ` ` `int` `mod[] = ` `new` `int` `[k];` ` ` `Arrays.fill(mod, ` `0` `);` ` ` `// Traverse original array and compute cumulative` ` ` `// sum take remainder of this current cumulative` ` ` `// sum and increase count by 1 for this remainder` ` ` `// in mod[] array` ` ` `int` `cumSum = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `cumSum += arr[i];` ` ` `// as the sum can be negative, taking modulo twice` ` ` `mod[((cumSum % k) + k) % k]++;` ` ` `}` ` ` `// Initialize result` ` ` `int` `result = ` `0` `;` ` ` `// Traverse mod[]` ` ` `for` `(` `int` `i = ` `0` `; i < k; i++)` ` ` `// If there are more than one prefix subarrays` ` ` `// with a particular mod value.` ` ` `if` `(mod[i] > ` `1` `)` ` ` `result += (mod[i] * (mod[i] - ` `1` `)) / ` `2` `;` ` ` `// add the elements which are divisible by k itself` ` ` `// i.e., the elements whose sum = 0` ` ` `result += mod[` `0` `];` ` ` `return` `result;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `arr[] = { ` `4` `, ` `5` `, ` `0` `, -` `2` `, -` `3` `, ` `1` `};` ` ` `int` `k = ` `5` `;` ` ` `int` `n = arr.length;` ` ` `System.out.println(subCount(arr, n, k));` ` ` `int` `arr1[] = { ` `4` `, ` `5` `, ` `0` `, -` `12` `, -` `23` `, ` `1` `};` ` ` `int` `k1 = ` `5` `;` ` ` `int` `n1 = arr1.length;` ` ` `System.out.println(subCount(arr1, n1, k1));` ` ` `}` `}` `// This code is contributed by Anant Agarwal.` |

## Python3

`# Python program to find` `# count of subarrays with` `# sum divisible by k.` `# Handles all the cases` `# function to find all` `# sub-arrays divisible by k` `# modified to handle` `# negative numbers as well` `def` `subCount(arr, n, k):` ` ` `# create auxiliary hash` ` ` `# array to count frequency` ` ` `# of remainders` ` ` `mod ` `=` `[]` ` ` `for` `i ` `in` `range` `(k ` `+` `1` `):` ` ` `mod.append(` `0` `)` ` ` ` ` `# Traverse original array` ` ` `# and compute cumulative` ` ` `# sum take remainder of this` ` ` `# current cumulative` ` ` `# sum and increase count by` ` ` `# 1 for this remainder` ` ` `# in mod[] array` ` ` `cumSum ` `=` `0` ` ` `for` `i ` `in` `range` `(n):` ` ` `cumSum ` `=` `cumSum ` `+` `arr[i]` ` ` ` ` `# as the sum can be negative,` ` ` `# taking modulo twice` ` ` `mod[((cumSum ` `%` `k)` `+` `k)` `%` `k]` `=` `mod[((cumSum ` `%` `k)` `+` `k)` `%` `k] ` `+` `1` ` ` ` ` ` ` `result ` `=` `0` `# Initialize result` ` ` ` ` `# Traverse mod[]` ` ` `for` `i ` `in` `range` `(k):` ` ` ` ` `# If there are more than` ` ` `# one prefix subarrays` ` ` `# with a particular mod value.` ` ` `if` `(mod[i] > ` `1` `):` ` ` `result ` `=` `result ` `+` `(mod[i]` `*` `(mod[i]` `-` `1` `))` `/` `/` `2` ` ` ` ` `# add the elements which` ` ` `# are divisible by k itself` ` ` `# i.e., the elements whose sum = 0` ` ` `result ` `=` `result ` `+` `mod[` `0` `]` ` ` ` ` `return` `result` ` ` `# driver code` `arr ` `=` `[` `4` `, ` `5` `, ` `0` `, ` `-` `2` `, ` `-` `3` `, ` `1` `]` `k ` `=` `5` `n ` `=` `len` `(arr)` `print` `(subCount(arr, n, k))` `arr1 ` `=` `[` `4` `, ` `5` `, ` `0` `, ` `-` `12` `, ` `-` `23` `, ` `1` `]` `k1 ` `=` `5` `n1 ` `=` `len` `(arr1)` `print` `(subCount(arr1, n1, k1))` `# This code is contributed` `# by Anant Agarwal.` |

## C#

`// C# program to find count of` `// subarrays with sum divisible by k.` `using` `System;` `class` `GFG {` ` ` `// Handles all the cases` ` ` `// function to find all sub-arrays divisible by k` ` ` `// modified to handle negative numbers as well` ` ` `static` `int` `subCount(` `int` `[] arr, ` `int` `n, ` `int` `k)` ` ` `{` ` ` `// create auxiliary hash array to` ` ` `// count frequency of remainders` ` ` `int` `[] mod = ` `new` `int` `[k];` ` ` ` ` `// Traverse original array and compute cumulative` ` ` `// sum take remainder of this current cumulative` ` ` `// sum and increase count by 1 for this remainder` ` ` `// in mod[] array` ` ` `int` `cumSum = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `cumSum += arr[i];` ` ` `// as the sum can be negative, taking modulo twice` ` ` `mod[((cumSum % k) + k) % k]++;` ` ` `}` ` ` `// Initialize result` ` ` `int` `result = 0;` ` ` `// Traverse mod[]` ` ` `for` `(` `int` `i = 0; i < k; i++)` ` ` `// If there are more than one prefix subarrays` ` ` `// with a particular mod value.` ` ` `if` `(mod[i] > 1)` ` ` `result += (mod[i] * (mod[i] - 1)) / 2;` ` ` `// add the elements which are divisible by k itself` ` ` `// i.e., the elements whose sum = 0` ` ` `result += mod[0];` ` ` `return` `result;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `[] arr = { 4, 5, 0, -2, -3, 1 };` ` ` `int` `k = 5;` ` ` `int` `n = arr.Length;` ` ` `Console.WriteLine(subCount(arr, n, k));` ` ` `int` `[] arr1 = { 4, 5, 0, -12, -23, 1 };` ` ` `int` `k1 = 5;` ` ` `int` `n1 = arr1.Length;` ` ` `Console.WriteLine(subCount(arr1, n1, k1));` ` ` `}` `}` `// This code is contributed by vt_m.` |

## Javascript

`<script>` ` ` `// Javascript program to find count of` ` ` `// subarrays with sum divisible by k.` ` ` ` ` `// Handles all the cases` ` ` `// function to find all sub-arrays divisible by k` ` ` `// modified to handle negative numbers as well` ` ` `function` `subCount(arr, n, k)` ` ` `{` ` ` `// create auxiliary hash array to` ` ` `// count frequency of remainders` ` ` `let mod = ` `new` `Array(k);` ` ` `mod.fill(0);` ` ` ` ` `// Traverse original array and compute cumulative` ` ` `// sum take remainder of this current cumulative` ` ` `// sum and increase count by 1 for this remainder` ` ` `// in mod[] array` ` ` `let cumSum = 0;` ` ` `for` `(let i = 0; i < n; i++) {` ` ` `cumSum += arr[i];` ` ` ` ` `// as the sum can be negative, taking modulo twice` ` ` `mod[((cumSum % k) + k) % k]++;` ` ` `}` ` ` ` ` `// Initialize result` ` ` `let result = 0;` ` ` ` ` `// Traverse mod[]` ` ` `for` `(let i = 0; i < k; i++)` ` ` ` ` `// If there are more than one prefix subarrays` ` ` `// with a particular mod value.` ` ` `if` `(mod[i] > 1)` ` ` `result += parseInt((mod[i] * (mod[i] - 1)) / 2, 10);` ` ` ` ` `// add the elements which are divisible by k itself` ` ` `// i.e., the elements whose sum = 0` ` ` `result += mod[0];` ` ` ` ` `return` `result;` ` ` `}` ` ` ` ` `let arr = [ 4, 5, 0, -2, -3, 1 ];` ` ` `let k = 5;` ` ` `let n = arr.length;` ` ` `document.write(subCount(arr, n, k) + ` `"</br>"` `);` ` ` `let arr1 = [ 4, 5, 0, -12, -23, 1 ];` ` ` `let k1 = 5;` ` ` `let n1 = arr1.length;` ` ` `document.write(subCount(arr1, n1, k1));` ` ` `</script>` |

Output:

7 7

Time complexity : O(n + k)

Auxiliary Space : O(k)**References **:

http://stackoverflow.com/questions/16605991/number-of-subarrays-divisible-by-k

This article is contributed by **Shashank Mishra ( Gullu )**. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.