Longest subarray with sum divisible by K
Last Updated :
02 Feb, 2023
Given an arr[] containing n integers and a positive integer k. The problem is to find the longest subarray’s length with the sum of the elements divisible by the given value k.
Examples:
Input: arr[] = {2, 7, 6, 1, 4, 5}, k = 3
Output: 4
Explanation: The subarray is {7, 6, 1, 4} with sum 18, which is divisible by 3.
Input: arr[] = {-2, 2, -5, 12, -11, -1, 7}, k = 3
Output: 5
Method 1 (Naive Approach): Consider all the subarrays and return the length of the subarray with a sum divisible by k that has the longest length.
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubarrWthSumDivByK(int arr[], int N, int k)
{
int maxl=0;
for(int i=0;i<N;i++)
{
int sum1 = 0;
for(int j=i;j<N;j++)
{
sum1+=arr[j];
if(sum1 % k == 0)
{
maxl = max(maxl , j - i + 1);
}
}
}
return maxl;
}
int main()
{
int arr[] = { 2, 7, 6, 1, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Length = "
<< longestSubarrWthSumDivByK(arr, n, k);
return 0;
}
|
Java
import java.util.*;
class GFG {
static int longestSubarrWthSumDivByK(int arr[], int N, int k)
{
int maxl = 0;
for (int i = 0; i < N; i++) {
int sum1 = 0;
for (int j = i; j < N; j++) {
sum1 += arr[j];
if (sum1 % k == 0)
maxl = Math.max(maxl, j - i + 1);
}
}
return maxl;
}
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 = "
+ longestSubarrWthSumDivByK(arr, n, k));
}
}
|
C#
using System;
class GFG {
static int longestSubarrWthSumDivByK(int[] arr, int N,
int k)
{
int maxl = 0;
for (int i = 0; i < N; i++) {
int sum1 = 0;
for (int j = i; j < N; j++) {
sum1 += arr[j];
if (sum1 % k == 0)
maxl = Math.Max(maxl, j - i + 1);
}
}
return maxl;
}
public static void Main(string[] args)
{
int[] arr = { 2, 7, 6, 1, 4, 5 };
int n = arr.Length;
int k = 3;
Console.WriteLine(
"Length = "
+ longestSubarrWthSumDivByK(arr, n, k));
}
}
|
Python3
def longestSubarrWthSumDivByK(arr, N, k):
maxl = 0
for i in range(N):
sum1 = 0
for j in range(i, N):
sum1 += arr[j]
if sum1 % k == 0:
maxl = max(maxl, j - i + 1)
return maxl
arr = [2, 7, 6, 1, 4, 5]
n = len(arr)
k = 3
print("Length =", longestSubarrWthSumDivByK(arr, n, k))
|
Javascript
function longestSubarrWthSumDivByK(arr, N, k) {
let maxl = 0;
for (let i = 0; i < N; i++) {
let sum1 = 0;
for (let j = i; j < N; j++) {
sum1 += arr[j];
if (sum1 % k === 0) {
maxl = Math.max(maxl, j - i + 1);
}
}
}
return maxl;
}
let arr = [ 2, 7, 6, 1, 4, 5 ];
let N = arr.length;
let k = 3;
console.log("Length = " + longestSubarrWthSumDivByK(arr, N, k));
|
Time Complexity: O(n2).
Auxiliary Space: O(1)
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, i), where ele represents an element of mod_arr[] and i 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.
- If mod_arr[i] == 0, then update max_len = (i + 1).
- Else if mod_arr[i] is not present in the hash table, then create tuple (mod_arr[i], i) in the hash table.
- Else, get the hash table’s value associated with mod_arr[i]. Let this be i.
- If maxLen < (i – idx), then update max_len = (i – idx).
- Finally, return max_len.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubarrWthSumDivByK(int arr[], int n, int k)
{
unordered_map<int, int> um;
int mod_arr[n], max_len = 0;
int curr_sum = 0;
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
mod_arr[i] = ((curr_sum % k) + k) % k;
if (mod_arr[i] == 0)
max_len = i + 1;
else if (um.find(mod_arr[i]) == um.end())
um[mod_arr[i]] = i;
else
if (max_len < (i - um[mod_arr[i]]))
max_len = i - um[mod_arr[i]];
}
return max_len;
}
int main()
{
int arr[] = { 2, 7, 6, 1, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Length = "
<< longestSubarrWthSumDivByK(arr, n, k);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GfG {
static int longestSubarrWthSumDivByK(int arr[], int n,
int k)
{
HashMap<Integer, Integer> um
= new HashMap<Integer, Integer>();
int mod_arr[] = new int[n];
int max_len = 0;
int curr_sum = 0;
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
mod_arr[i] = ((curr_sum % k) + k) % k;
if (mod_arr[i] == 0)
max_len = i + 1;
else if (um.containsKey(mod_arr[i]) == false)
um.put(mod_arr[i], i);
else
if (max_len < (i - um.get(mod_arr[i])))
max_len = i - um.get(mod_arr[i]);
}
return max_len;
}
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 = "
+ longestSubarrWthSumDivByK(arr, n, k));
}
}
|
Python3
def longestSubarrWthSumDivByK(arr, n, k):
um = {}
mod_arr = [0 for i in range(n)]
max_len = 0
curr_sum = 0
for i in range(n):
curr_sum += arr[i]
mod_arr[i] = ((curr_sum % k) + k) % k
if (mod_arr[i] == 0):
max_len = i + 1
elif (mod_arr[i] not in um):
um[mod_arr[i]] = i
else:
if (max_len < (i - um[mod_arr[i]])):
max_len = i - um[mod_arr[i]]
return max_len
if __name__ == '__main__':
arr = [2, 7, 6, 1, 4, 5]
n = len(arr)
k = 3
print("Length =",
longestSubarrWthSumDivByK(arr, n, k))
|
C#
using System;
using System.Collections.Generic;
public class GfG {
public static int
longestSubarrWthSumDivByK(int[] arr, int n, int k)
{
Dictionary<int, int> um
= new Dictionary<int, int>();
int[] mod_arr = new int[n];
int max_len = 0;
int curr_sum = 0;
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
mod_arr[i] = ((curr_sum % k) + k) % k;
if (mod_arr[i] == 0) {
max_len = i + 1;
}
else if (um.ContainsKey(mod_arr[i]) == false) {
um[mod_arr[i]] = i;
}
else {
if (max_len < (i - um[mod_arr[i]])) {
max_len = i - um[mod_arr[i]];
}
}
}
return max_len;
}
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 = "
+ longestSubarrWthSumDivByK(arr, n, k));
}
}
|
Javascript
<script>
function longestSubarrWthSumDivByK(arr, n, k)
{
var um = new Map();
var mod_arr = Array(n), max_len = 0;
var curr_sum = 0;
for (var i = 0; i < n; i++)
{
curr_sum += arr[i];
mod_arr[i] = ((curr_sum % k) + k) % k;
if (mod_arr[i] == 0)
max_len = i + 1;
else if (!um.has(mod_arr[i]))
um.set(mod_arr[i] , i);
else
if (max_len < (i - um.get(mod_arr[i])))
max_len = i - um.get(mod_arr[i]);
}
return max_len;
}
var arr = [2, 7, 6, 1, 4, 5];
var n = arr.length;
var k = 3;
document.write( "Length = "
+ longestSubarrWthSumDivByK(arr, n, k));
</script>
|
Time Complexity: O(n), as we traverse the input array only once.
Auxiliary Space: O(n + k), O(n) for mod_arr[], and O(k) for storing the remainder values in the hash table.
Space Optimized approach: The space optimization for the above approach to O(n) Instead of keeping a separate array to store the modulus of all values, we compute it on the go and store remainders in the hash table.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubarrWthSumDivByK(int arr[], int n, int k)
{
unordered_map<int, int> um;
int max_len = 0;
int curr_sum = 0;
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
int mod = ((curr_sum % k) + k) % k;
if (mod == 0)
max_len = i + 1;
else if (um.find(mod) == um.end())
um[mod] = i;
else
if (max_len < (i - um[mod]))
max_len = i - um[mod];
}
return max_len;
}
int main()
{
int arr[] = { 2, 7, 6, 1, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Length = "
<< longestSubarrWthSumDivByK(arr, n, k);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static int longestSubarrWthSumDivByK(int arr[], int n,
int k)
{
Map<Integer, Integer> map = new HashMap<>();
int max_len = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
int mod = ((sum % k) + k) % k;
if (mod == 0)
max_len = i + 1;
if (!map.containsKey(mod))
map.put(mod, i);
else {
int sz = i - map.get(mod);
max_len = Math.max(max_len, sz);
}
}
return max_len;
}
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 = "
+ longestSubarrWthSumDivByK(arr, n, k));
}
}
|
Python3
def longestSubarrWthSumDivByK(arr, n, k):
um = {}
max_len = 0
curr_sum = 0
for i in range(n):
curr_sum += arr[i]
mod = ((curr_sum % k) + k) % k
if mod == 0:
max_len = i + 1
elif mod in um.keys():
if max_len < (i - um[mod]):
max_len = i - um[mod]
else:
um[mod] = i
return max_len
arr = [2, 7, 6, 1, 4, 5]
n = len(arr)
k = 3
print("Length =", longestSubarrWthSumDivByK(arr, n, k))
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public static int
longestSubarrWthSumDivByK(int[] arr, int n, int k)
{
Dictionary<int, int> um
= new Dictionary<int, int>();
int max_len = 0;
int curr_sum = 0;
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
int mod = ((curr_sum % k) + k) % k;
if (mod == 0)
{
max_len = i + 1;
}
else if (um.ContainsKey(mod) == false) {
um[mod] = i;
}
else {
if (max_len < (i - um[mod])) {
max_len = i - um[mod];
}
}
}
return max_len;
}
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 = "
+ longestSubarrWthSumDivByK(arr, n, k));
}
}
|
Javascript
<script>
function longestSubarrWthSumDivByK(arr,n,k)
{
let um = new Map();
let max_len = 0;
let curr_sum = 0;
for (let i = 0; i < n; i++)
{
curr_sum += arr[i];
let mod = ((curr_sum % k) + k) % k;
if (mod == 0)
max_len = i + 1;
else if (um.has(mod) == false)
um.set(mod,i);
else
if (max_len < (i - um.get(mod)))
max_len = i - um.get(mod);
}
return max_len;
}
let arr = [2, 7, 6, 1, 4, 5];
let n = arr.length;
let k = 3;
document.write("Length = " + longestSubarrWthSumDivByK(arr, n, k));
</script>
|
Time Complexity: O(n), as we traverse the input array only once.
Auxiliary Space: O(min(n,k))
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...