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++

// C++ implementation to find the longest subarray
// with sum divisible by k
 
#include <bits/stdc++.h>
using namespace std;
 
// function to find the longest subarray
// with sum divisible by k
 
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;
}
 
// Driver code
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;
}
 
// This code is contributed by Arpit Jain

Java

import java.util.*;
 
class GFG {
 
  // function to find the longest subarray
  // with sum divisible by k
  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;
  }
 
  // Driver code
  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));
  }
}
 
// This code is contributed by Ajax

C#

// C# implementation to find the longest subarray
// with sum divisible by k
 
using System;
 
class GFG {
 
    // function to find the longest subarray
    // with sum divisible by k
    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;
    }
 
    // Driver code
    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));
    }
}
 
// This code is contributed by Karandeep1234

Python3

# Python3 implementation to find the longest subarray
# with sum divisible by k
 
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
 
# Driver code
arr = [2, 7, 6, 1, 4, 5]
n = len(arr)
k = 3
 
print("Length =", longestSubarrWthSumDivByK(arr, n, k))

Javascript

// JavaScript implementation to find the longest subarray
// with sum divisible by k
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;
}
 
// Driver code
let arr = [ 2, 7, 6, 1, 4, 5 ];
let N = arr.length;
let k = 3;
console.log("Length = " + longestSubarrWthSumDivByK(arr, N, k));
 
//This code is contributed by dhanshri borse

Output

Length = 4

Time Complexity: O(n²).
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++

// C++ implementation to find the longest subarray
// with sum divisible by k
 
#include <bits/stdc++.h>
using namespace std;
 
// function to find the longest subarray
// with sum divisible by k
 
int longestSubarrWthSumDivByK(int arr[], int n, int k)
{
    // unordered map 'um' implemented as
    // hash table
    unordered_map<int, int> um;
 
    // 'mod_arr[i]' stores (sum[0..i] % k)
    int mod_arr[n], max_len = 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;
 
        // if true then sum(0..i) is divisible by k
        if (mod_arr[i] == 0)
            // update 'max'
            max_len = 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_len < (i - um[mod_arr[i]]))
            max_len = i - um[mod_arr[i]];
    }
 
    // return the required length of longest subarray
    // with sum divisible by 'k'
    return max_len;
}
 
// Driver code
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;
}
 
// Code updated by Kshitij Dwivedi

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 longestSubarrWthSumDivByK(int arr[], int n,
                                         int k)
    {
        // unordered map 'um' implemented as
        // hash table
        HashMap<Integer, Integer> um
            = new HashMap<Integer, Integer>();
 
        // 'mod_arr[i]' stores (sum[0..i] % k)
        int mod_arr[] = new int[n];
        int max_len = 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;
 
            // if true then sum(0..i) is
            // divisible by k
            if (mod_arr[i] == 0)
                // update 'max'
                max_len = 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_len < (i - um.get(mod_arr[i])))
                max_len = i - um.get(mod_arr[i]);
        }
 
        // return the required length of longest subarray
        // with sum divisible by 'k'
        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));
    }
}
 
// This code is contributed by Gitanjali, updated by Kshitij
// Dwivedi

Python3

# Python3 implementation to find the
# longest subarray with sum divisible by k
 
# Function to find the longest
# subarray with sum divisible by k
 
 
def longestSubarrWthSumDivByK(arr, n, k):
 
    # unordered map 'um' implemented
    # as hash table
    um = {}
 
    # 'mod_arr[i]' stores (sum[0..i] % k)
    mod_arr = [0 for i in range(n)]
    max_len = 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
 
        # If true then sum(0..i) is
        # divisible by k
        if (mod_arr[i] == 0):
 
            # Update 'max_len'
            max_len = 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] not in um):
            um[mod_arr[i]] = i
 
        else:
              # If true, then update 'max_len'
            if (max_len < (i - um[mod_arr[i]])):
                max_len = i - um[mod_arr[i]]
 
    # Return the required length of longest subarray
    # with sum divisible by 'k'
    return max_len
 
 
# Driver Code
if __name__ == '__main__':
 
    arr = [2, 7, 6, 1, 4, 5]
    n = len(arr)
    k = 3
 
    print("Length =",
          longestSubarrWthSumDivByK(arr, n, k))
 
# This code is contributed by Surendra_Gangwar, updated by Kshitij Dwivedi

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
    longestSubarrWthSumDivByK(int[] arr, int n, int k)
    {
        // unordered 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_len = 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,
            // adjusting and calculating modulo twice
            mod_arr[i] = ((curr_sum % k) + k) % k;
 
            // if true then sum(0..i) is
            // divisible by k
            if (mod_arr[i] == 0) {
                // update 'max_len'
                max_len = 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_len'
                if (max_len < (i - um[mod_arr[i]])) {
                    max_len = i - um[mod_arr[i]];
                }
            }
        }
 
        // return the required length of longest subarray
        // with sum divisible by 'k'
        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));
    }
}
 
// This code is contributed by Shrikant13, updated by
// Kshitij Dwivedi

Javascript

<script>
 
// Javascript implementation to find the longest subarray
// with sum divisible by k
 
// function to find the longest subarray
// with sum divisible by k
function longestSubarrWthSumDivByK(arr, n, k)
{
    // unordered map 'um' implemented as
    // hash table
    var um = new Map();
     
    // 'mod_arr[i]' stores (sum[0..i] % k)
    var mod_arr = Array(n), max_len = 0;
    var curr_sum = 0;
     
    // traverse arr[] and build up the
    // array 'mod_arr[]'
    for (var 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;        
 
        // if true then sum(0..i) is divisible
        // by k
        if (mod_arr[i] == 0)
            // update 'max_len'
            max_len = 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.has(mod_arr[i]))
            um.set(mod_arr[i] , i);
             
        else
            // if true, then update 'max_len'
            if (max_len < (i - um.get(mod_arr[i])))
                max_len = i - um.get(mod_arr[i]);            
    }
     
    // return the required length of longest subarray with
    // sum divisible by 'k'
    return max_len;
}                          
 
// Driver program to test above
var arr = [2, 7, 6, 1, 4, 5];
var n = arr.length;
var k = 3;
 
document.write( "Length = "
     + longestSubarrWthSumDivByK(arr, n, k));
      
// This code is contributed by rrrtnx, and updated by Kshitij Dwivedi
</script>

Output

Length = 4

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;
 
// function to find the longest subarray
// with sum divisible by k
int longestSubarrWthSumDivByK(int arr[], int n, int k)
{
    // unordered map 'um' implemented as
    // hash table
    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 true then sum(0..i) is divisible
        // by k
        if (mod == 0)
            // update 'max_len'
            max_len = 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) == um.end())
            um[mod] = i;
 
        else
            // if true, then update 'max_len'
            if (max_len < (i - um[mod]))
            max_len = i - um[mod];
    }
 
    // return the required length of longest subarray with
    // sum divisible by 'k'
    return max_len;
}
 
// Driver code
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;
}
 
// Code Updated by Kshitij Dwivedi

Java

/*package whatever //do not write package name here */
 
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];
 
            // to handle negative values as well
            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));
    }
}
 
// Updated By Kshitij Dwivedi

Python3

# function to find the longest subarray
#  with sum divisible by k
 
 
def longestSubarrWthSumDivByK(arr, n, k):
 
    # unordered map 'um' implemented as
    # hash table
    um = {}
 
    max_len = 0
    curr_sum = 0
 
    for i in range(n):
 
        curr_sum += arr[i]
        mod = ((curr_sum % k) + k) % k
        # if true then sum(0..i) is divisible by k
 
        if mod == 0:
            # update 'max_len'
            max_len = i + 1
 
        # if value 'mod_arr[i]' not present in 'um'
        # then store it in 'um' with index of its
        # first occurrence
        elif mod in um.keys():
            if max_len < (i - um[mod]):
                max_len = i - um[mod]
 
        else:
            um[mod] = i
 
    # return the required length of longest subarray with
    # sum divisible by 'k'
    return max_len
 
 
arr = [2, 7, 6, 1, 4, 5]
n = len(arr)
k = 3
print("Length =", longestSubarrWthSumDivByK(arr, n, k))
 
# This code is contributed by amreshkumar3, and updated by Kshitij Dwivedi

C#

using System;
using System.Collections.Generic;
 
// C# implementation to find the longest
// subarray with sum divisible by k
public class GFG {
 
    public static int
    longestSubarrWthSumDivByK(int[] arr, int n, int k)
    {
        // unordered map 'um' implemented as
        // hash table
        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 true then sum(0..i) is divisible
            // by k
            if (mod == 0)
            // update 'max_len'
            {
                max_len = i + 1;
            }
 
            // if value 'mod' not present in 'um'
            // then store it in 'um' with index of its
            // first occurrence
            else if (um.ContainsKey(mod) == false) {
                um[mod] = i;
            }
 
            else {
                // if true, then update 'max'
                if (max_len < (i - um[mod])) {
                    max_len = i - um[mod];
                }
            }
        }
        // return the required length of longest subarray
        // with sum divisible by 'k'
        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));
    }
}
 
// This code is contributed by ishankhandelwals and updated
// by Kshitij Dwivedi

Javascript

<script>
// function to find the longest subarray
// with sum divisible by k
function longestSubarrWthSumDivByK(arr,n,k)
{
    // map 'um' implemented as
    // hash table
    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 true then sum(0..i) is divisible
        // by k
        if (mod == 0)
            // update 'max_len'
            max_len = 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.has(mod) == false)
            um.set(mod,i);
 
        else
            // if true, then update 'max'
            if (max_len < (i - um.get(mod)))
            max_len = i - um.get(mod);
    }
 
    // required length of longest subarray with
    // sum divisible by 'k'
    return max_len;
}
 
// Driver program to test above
 
let arr = [2, 7, 6, 1, 4, 5];
let n = arr.length;
let k = 3;
 
document.write("Length = " + longestSubarrWthSumDivByK(arr, n, k));
 
// This code is contributed by shinjanpatra, and updated by Kshitij Dwivedi.
</script>

Output

Length = 4

Time Complexity: O(n), as we traverse the input array only once.
Auxiliary Space: O(min(n,k))

A

ayushjauhari14

Improve

Previous Article

Find number of Employees Under every Manager

Find the length of largest subarray with 0 sum

Similar Reads

Longest subarray with sum not divisible by X

Given an array arr[] and an integer X, the task is to print the longest subarray such that the sum of its elements isn't divisible by X. If no such subarray exists, print "-1". Note: If more than one subarray exists with the given property, print any one of them.Examples: Input: arr[] = {1, 2, 3} X = 3 Output: 2 3 Explanation: The subarray {2, 3} h

Length of longest subarray whose sum is not divisible by integer K

Given an array arr[] of size N and an integer k, our task is to find the length of longest subarray whose sum of elements is not divisible by k. If no such subarray exists then return -1.Examples: Input: arr[] = {8, 4, 3, 1, 5, 9, 2}, k = 2 Output: 5 Explanation: The subarray is {8, 4, 3, 1, 5} with sum = 21, is not divisible by 2.Input: arr[] = {6

Longest subarray with elements divisible by k

Suppose you are given an array. You have to find the length of the longest subarray such that each and every element of it is divisible by k.Examples: Input : arr[] = { 1, 7, 2, 6, 8, 100, 3, 6, 16}, k=2Output : 4 Input : arr[] = { 3, 11, 22, 32, 55, 100, 1, 5}, k=5Output : 2 Approach: Initialize two variables current_count and max_count with value

Max sum of Subarray of length N/2 where sum is divisible by N

Given an array, arr[] of size N where N is even, the task is to find the maximum possible sum of the subarray of length N/2 where the sum is divisible by N. Examples: Input: arr[] = {2, 3, 4, 5, 6, 7}, N = 6Output:18Explanation: Here, N = 6, The maximum possible sum of a sublist of length 3 (N/2) is 18 (divisible by 6), which can be obtained by sel

First subarray having sum at least half the maximum sum of any subarray of size K

Given an array arr[] and an integer K, the task is to find the first subarray which has a sum greater than or equal to half of the maximum possible sum from any subarray of size K. Examples: Input: arr[] = {2, 4, 5, 1, 4, 6, 6, 2, 1, 0}, K = 3 Output: 6 2 1 Explanation: The given array has a maximum possible sum from any subarray of size K is 16 fr

Find a subarray whose sum is divisible by size of the array

Given an array arr[] of length N. The task is to check if there exists any subarray whose sum is a multiple of N. If there exists such subarray, then print the starting and ending index of that subarray else print -1. If there are multiple such subarrays, print any of them. Examples: Input: arr[] = {7, 5, 3, 7} Output: 0 1 Sub-array from index 0 to

Length of smallest subarray to be removed to make sum of remaining elements divisible by K

Given an array arr[] of integers and an integer K, the task is to find the length of the smallest subarray that needs to be removed such that the sum of remaining array elements is divisible by K. Removal of the entire array is not allowed. If it is impossible, then print "-1". Examples: Input: arr[] = {3, 1, 4, 2}, K = 6Output: 1Explanation: Sum o

Generate an N-length array having sum of each subarray divisible by K

Given two positive integers N and K, the task is to generate an array consisting of N distinct integers such that the sum of elements of each subarray of the constructed array is divisible by K. Examples: Input: N = 3, K = 3Output: 3 6 9Explanation:The subarrays of the resultant array are {3}, {6}, {3, 6}, {9}, {6, 9}, {3, 6, 9}. Sum of all these s

Count ways to split an array into subarrays such that sum of the i-th subarray is divisible by i

Given an array arr[] consisting of N integers, the task is to find the number of ways to split the array into non-empty subarrays such that the sum of the ith subarray is divisible by i. Examples: Input: arr[] = {1, 2, 3, 4}Output: 3Explanation:Following are the number of ways to split the array into non-empty subarray as: Split the array into suba

Non-Divisible Subarray sum permutation

Given a positive integer X, the task is to find a permutation of length X such that all subarray sum of length greater than one is not divisible by subarray length. If no permutation of length X exists, then print "Permutation doesn't exist". Examples: Input: X = 4Output: {2, 1, 4, 3}Explanation: All subarray sum of length greater than 1 isn't divi

Article Tags :

Practice Tags :