# Longest subarray with sum divisible by k

Given an arr[] containing n integers and a positive integer k. The problem is to find the length of the longest subarray with sum of the elements divisible by the given value k.

Examples:

```Input : arr[] = {2, 7, 6, 1, 4, 5}, k = 3
Output : 4
The subarray is {7, 6, 1, 4} with sum 18,
which is divisible by 3.

Input : arr[] = {-2, 2, -5, 12, -11, -1, 7}
Output : 5
```

Method 1 (Naive Approach): Consider all the subarrays and return the length of the subarray with sum divisible by k and has the longest length.
Time Complexity: O(n2).

Method 2 (Efficient Approach): Create an array mod_arr[] where mod_arr[i] stores (sum(arr[0]+arr[1]..+arr[i]) % k). Create a hash table having tuple as (ele, idx), where ele represents an element of mod_arr[] and idx represents the element’s index of first occurrence in mod_arr[]. Now, traverse mod_arr[] from i = 0 to n and follow the steps given below.

1. If mod_arr[i] == 0, then update maxLen = (i + 1).
2. Else if mod_arr[i] is not present in the hash table, then create tuple (mod_arr[i], i) in the hash table.
3. Else, get the value associated with mod_arr[i] in the hash table. Let this be idx.
4. If maxLen < (i – idx), then update maxLen = (i – idx).

Finally return maxLen.

## C++

 `// C++ implementation to find the longest subarray ` `// with sum divisible by k ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// function to find the longest subarray ` `// with sum divisible by k ` `int` `longSubarrWthSumDivByK(``int` `arr[],  ` `                          ``int` `n, ``int` `k) ` `{ ` `    ``// unodered map 'um' implemented as ` `    ``// hash table ` `    ``unordered_map<``int``, ``int``> um; ` `     `  `    ``// 'mod_arr[i]' stores (sum[0..i] % k) ` `    ``int` `mod_arr[n], max = 0; ` `    ``int` `curr_sum = 0; ` `     `  `    ``// traverse arr[] and build up the ` `    ``// array 'mod_arr[]' ` `    ``for` `(``int` `i = 0; i < n; i++) ` `    ``{ ` `        ``curr_sum += arr[i]; ` `         `  `        ``// as the sum can be negative, taking modulo twice ` `        ``mod_arr[i] = ((curr_sum % k) + k) % k;         ` `    ``}     ` `     `  `    ``for` `(``int` `i = 0; i < n; i++) ` `    ``{ ` `        ``// if true then sum(0..i) is divisible ` `        ``// by k ` `        ``if` `(mod_arr[i] == 0) ` `            ``// update 'max' ` `            ``max = i + 1; ` `         `  `        ``// if value 'mod_arr[i]' not present in 'um' ` `        ``// then store it in 'um' with index of its ` `        ``// first occurrence         ` `        ``else` `if` `(um.find(mod_arr[i]) == um.end()) ` `            ``um[mod_arr[i]] = i; ` `             `  `        ``else` `            ``// if true, then update 'max' ` `            ``if` `(max < (i - um[mod_arr[i]])) ` `                ``max = i - um[mod_arr[i]];             ` `    ``} ` `     `  `    ``// required length of longest subarray with ` `    ``// sum divisible by 'k' ` `    ``return` `max; ` `}                           ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``int` `arr[] = {2, 7, 6, 1, 4, 5}; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `    ``int` `k = 3; ` `     `  `    ``cout << ``"Length = "` `         ``<< longSubarrWthSumDivByK(arr, n, k); ` `          `  `    ``return` `0;      ` `} `

## Java

 `// Java implementation to find the longest  ` `// subarray with sum divisible by k ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GfG { ` `         `  `    ``// function to find the longest subarray ` `    ``// with sum divisible by k ` `    ``static` `int` `longSubarrWthSumDivByK(``int` `arr[],  ` `                                      ``int` `n, ``int` `k) ` `    ``{ ` `        ``// unodered map 'um' implemented as ` `        ``// hash table ` `        ``HashMap um= ``new` `HashMap(); ` `         `  `        ``// 'mod_arr[i]' stores (sum[0..i] % k) ` `        ``int` `mod_arr[]= ``new` `int``[n]; ` `        ``int` `max = ``0``; ` `        ``int` `curr_sum = ``0``; ` `         `  `        ``// traverse arr[] and build up the ` `        ``// array 'mod_arr[]' ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `        ``{ ` `            ``curr_sum += arr[i]; ` `             `  `            ``// as the sum can be negative,  ` `            ``// taking modulo twice ` `            ``mod_arr[i] = ((curr_sum % k) + k) % k;      ` `        ``}  ` `         `  `        ``for` `(``int` `i = ``0``; i < n; i++) ` `        ``{ ` `            ``// if true then sum(0..i) is  ` `            ``// divisible by k ` `            ``if` `(mod_arr[i] == ``0``) ` `                ``// update 'max' ` `                ``max = i + ``1``; ` `             `  `            ``// if value 'mod_arr[i]' not present in 'um' ` `            ``// then store it in 'um' with index of its ` `            ``// first occurrence      ` `            ``else` `if` `(um.containsKey(mod_arr[i]) == ``false``) ` `                ``um.put(mod_arr[i] , i); ` `                 `  `            ``else` `                ``// if true, then update 'max' ` `                ``if` `(max < (i - um.get(mod_arr[i]))) ` `                    ``max = i - um.get(mod_arr[i]);          ` `        ``} ` `         `  `        ``// required length of longest subarray with ` `        ``// sum divisible by 'k' ` `        ``return` `max; ` `    ``}     ` `     `  `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `arr[] = {``2``, ``7``, ``6``, ``1``, ``4``, ``5``}; ` `        ``int` `n = arr.length; ` `        ``int` `k = ``3``; ` `         `  `        ``System.out.println(``"Length = "``+  ` `                            ``longSubarrWthSumDivByK(arr, n, k)); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by Gitanjali. `

## Python3

# Python 3 implementation to find the
# longest subarray with sum divisible by k

# function to find the longest
# subarray with sum divisible by k
def longSubarrWthSumDivByK(arr, n, k):

# unodered map ‘um’ implemented
# as hash table
um = {i:0 for i in range(8)}

# ‘mod_arr[i]’ stores (sum[0..i] % k)
mod_arr = [0 for i in range(n)]
max = 0
curr_sum = 0

# traverse arr[] and build up
# the array ‘mod_arr[]’
for i in range(n):
curr_sum += arr[i]

# as the sum can be negative,
# taking modulo twice
mod_arr[i] = ((curr_sum % k) + k) % k

for i in range(n):

# if true then sum(0..i) is
# divisible by k
if (mod_arr[i] == 0):

# update ‘max’
max = i + 1

# if value ‘mod_arr[i]’ not present in
# ‘um’ then store it in ‘um’ with index
# of its first occurrence
elif (mod_arr[i] in um):
um[mod_arr[i]] = i

else:

# if true, then update ‘max’
if (max < (i - um[mod_arr[i]])): max = i - um[mod_arr[i]] # required length of longest subarray # with sum divisible by 'k' return max # Driver Code if __name__ == '__main__': arr = [2, 7, 6, 1, 4, 5] n = len(arr) k = 3 print("Length =", longSubarrWthSumDivByK(arr, n, k)) # This code is contributed by # Surendra_Gangwar [tabby title="C#"]

 `using` `System; ` `using` `System.Collections.Generic; ` ` `  `// C# implementation to find the longest   ` `// subarray with sum divisible by k  ` ` `  `public` `class` `GfG ` `{ ` ` `  `    ``// function to find the longest subarray  ` `    ``// with sum divisible by k  ` `    ``public` `static` `int` `longSubarrWthSumDivByK(``int``[] arr, ``int` `n, ``int` `k) ` `    ``{ ` `        ``// unodered map 'um' implemented as  ` `        ``// hash table  ` `        ``Dictionary<``int``, ``int``> um = ``new` `Dictionary<``int``, ``int``>(); ` ` `  `        ``// 'mod_arr[i]' stores (sum[0..i] % k)  ` `        ``int``[] mod_arr = ``new` `int``[n]; ` `        ``int` `max = 0; ` `        ``int` `curr_sum = 0; ` ` `  `        ``// traverse arr[] and build up the  ` `        ``// array 'mod_arr[]'  ` `        ``for` `(``int` `i = 0; i < n; i++) ` `        ``{ ` `            ``curr_sum += arr[i]; ` ` `  `            ``// as the sum can be negative,   ` `            ``// taking modulo twice  ` `            ``mod_arr[i] = ((curr_sum % k) + k) % k; ` `        ``} ` ` `  `        ``for` `(``int` `i = 0; i < n; i++) ` `        ``{ ` `            ``// if true then sum(0..i) is   ` `            ``// divisible by k  ` `            ``if` `(mod_arr[i] == 0) ` `            ``{ ` `                ``// update 'max'  ` `                ``max = i + 1; ` `            ``} ` ` `  `            ``// if value 'mod_arr[i]' not present in 'um'  ` `            ``// then store it in 'um' with index of its  ` `            ``// first occurrence       ` `            ``else` `if` `(um.ContainsKey(mod_arr[i]) == ``false``) ` `            ``{ ` `                ``um[mod_arr[i]] = i; ` `            ``} ` ` `  `            ``else` `            ``{ ` `                ``// if true, then update 'max'  ` `                ``if` `(max < (i - um[mod_arr[i]])) ` `                ``{ ` `                    ``max = i - um[mod_arr[i]]; ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// required length of longest subarray with  ` `        ``// sum divisible by 'k'  ` `        ``return` `max; ` `    ``} ` ` `  `    ``public` `static` `void` `Main(``string``[] args) ` `    ``{ ` `        ``int``[] arr = ``new` `int``[] {2, 7, 6, 1, 4, 5}; ` `        ``int` `n = arr.Length; ` `        ``int` `k = 3; ` ` `  `        ``Console.WriteLine(``"Length = "` `+ longSubarrWthSumDivByK(arr, n, k)); ` ` `  `    ``} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

```Length = 3
```

Time Complexity: O(n).
Auxiliary Space: O(n^2).

Time complexity of this method can be improved by using an array of size equal to k for O(1) lookup since all elements would be less than k after using modulo operation on elements of input array.

## tags:

Arrays Hash Arrays Hash