Longest subarray with elements having equal modulo K

0 0 8 minutes read

Given an integer K and an array arr of integer elements, the task is to print the length of the longest sub-array such that each element of this sub-array yields same remainder upon division by K.

Examples:

Input: arr[] = {2, 1, 5, 8, 1}, K = 3
Output: 2
{2, 1, 5, 8, 1} gives remainders {2, 1, 2, 2, 1} on division with 3
Hence, longest sub-array length is 2.

Input: arr[] = {1, 100, 2, 9, 4, 32, 6, 3}, K = 2
Output: 3

Simple Approach:

Traverse the array from left to right and store modulo of each element with K in second array.
Now the task is reduced to find the longest sub-array with same elements.

Below is the implementation of the above approach:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to find longest sub-array
// whose elements gives same remainder
// when divided with K
int LongestSubarray(int arr[], int n, int k)
{
    // second array contains modulo
    // results of each element with K
    int arr2[n];
    for (int i = 0; i < n; i++)
        arr2[i] = arr[i] % k;
 
    int current_length, max_length = 0;
    int j;
 
    // loop for finding longest sub-array
    // with equal elements
    for (int i = 0; i < n;) {
        current_length = 1;
        for (j = i + 1; j < n; j++) {
            if (arr2[j] == arr2[i])
                current_length++;
            else
                break;
        }
        max_length = max(max_length, current_length);
        i = j;
    }
    return max_length;
}
 
// Driver code
int main()
{
    int arr[] = { 4, 9, 7, 18, 29, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 11;
    cout << LongestSubarray(arr, n, k);
    return 0;
}

Java

//  Java implementation of above approach
import java .io.*;
 
class GFG
{
// function to find longest sub-array
// whose elements gives same remainder
// when divided with K
static int LongestSubarray(int[] arr, 
                        int n, int k)
{
    // second array contains modulo
    // results of each element with K
    int[] arr2 = new int[n];
    for (int i = 0; i < n; i++)
        arr2[i] = arr[i] % k;
 
    int current_length, max_length = 0;
    int j;
 
    // loop for finding longest 
    // sub-array with equal elements
    for (int i = 0; i < n;) 
    {
        current_length = 1;
        for (j = i + 1; j < n; j++) 
        {
            if (arr2[j] == arr2[i])
                current_length++;
            else
                break;
        }
        max_length = Math.max(max_length, 
                            current_length);
        i = j;
    }
    return max_length;
}
 
// Driver code
public static void main(String[] args)
{
    int[] arr = { 4, 9, 7, 18, 29, 11 };
    int n = arr.length;
    int k = 11;
    System.out.println(LongestSubarray(arr, n, k));
}
}
 
// This code is contributed 
// by shs

Python 3

# Python 3 implementation of above approach
 
# function to find longest sub-array
# whose elements gives same remainder
# when divided with K
def LongestSubarray(arr, n, k):
 
    # second array contains modulo
    # results of each element with K
    arr2 = [0] * n
    for i in range( n):
        arr2[i] = arr[i] % k
         
    max_length = 0
 
    # loop for finding longest sub-array
    # with equal elements
    i = 0
    while i < n :
        current_length = 1
        for j in range(i + 1, n):
            if (arr2[j] == arr2[i]):
                current_length += 1
            else:
                break
         
        max_length = max(max_length, 
                         current_length)
        i = j
        i += 1
 
    return max_length
 
# Driver code
if __name__ == "__main__":
    arr = [ 4, 9, 7, 18, 29, 11 ]
    n = len(arr)
    k = 11
    print(LongestSubarray(arr, n, k))
 
# This code is contributed 
# by ChitraNayal

C#

// C# implementation of above approach
using System;
 
class GFG
{
// function to find longest sub-array
// whose elements gives same remainder
// when divided with K
static int LongestSubarray(int[] arr, 
                           int n, int k)
{
    // second array contains modulo
    // results of each element with K
    int[] arr2 = new int[n];
    for (int i = 0; i < n; i++)
        arr2[i] = arr[i] % k;
 
    int current_length, max_length = 0;
    int j;
 
    // loop for finding longest 
    // sub-array with equal elements
    for (int i = 0; i < n;) 
    {
        current_length = 1;
        for (j = i + 1; j < n; j++) 
        {
            if (arr2[j] == arr2[i])
                current_length++;
            else
                break;
        }
        max_length = Math.Max(max_length,   
                              current_length);
        i = j;
    }
    return max_length;
}
 
// Driver code
public static void Main()
{
    int[] arr = { 4, 9, 7, 18, 29, 11 };
    int n = arr.Length;
    int k = 11;
    Console.Write(LongestSubarray(arr, n, k));
}
}
 
// This code is contributed 
// by Akanksha Rai

PHP

<?php
// PHP implementation of above approach
 
// function to find longest sub-array
// whose elements gives same remainder
// when divided with K
function LongestSubarray($arr, $n, $k)
{
    // second array contains modulo
    // results of each element with K
    $arr2[$n] = array();
    for ($i = 0; $i < $n; $i++)
        $arr2[$i] = $arr[$i] % $k;
 
    $current_length;
    $max_length = 0;
    $j;
 
    // loop for finding longest sub-array
    // with equal elements
    for ($i = 0; $i < $n😉 
    {
        $current_length = 1;
        for ($j = $i + 1; $j < $n; $j++)
        {
            if ($arr2[$j] == $arr2[$i])
                $current_length++;
            else
                break;
        }
        $max_length = max($max_length, 
                          $current_length);
        $i = $j;
    }
    return $max_length;
}
 
// Driver code
$arr = array( 4, 9, 7, 18, 29, 11 );
$n = sizeof($arr);
$k = 11;
echo LongestSubarray($arr, $n, $k);
 
// This code is contributed
// by Sach_Code
?>

Javascript

<script>
 
// Javascript implementation of above approach
 
// function to find longest sub-array
// whose elements gives same remainder
// when divided with K
function LongestSubarray(arr, n, k)
{
    // second array contains modulo
    // results of each element with K
    var arr2 = Array(n);
    for (var i = 0; i < n; i++)
        arr2[i] = arr[i] % k;
 
    var current_length, max_length = 0;
    var j;
 
    // loop for finding longest sub-array
    // with equal elements
    for (var i = 0; i < n;) {
        current_length = 1;
        for (j = i + 1; j < n; j++) {
            if (arr2[j] == arr2[i])
                current_length++;
            else
                break;
        }
        max_length = Math.max(max_length, current_length);
        i = j;
    }
    return max_length;
}
 
// Driver code
var arr = [4, 9, 7, 18, 29, 11 ];
var n = arr.length;
var k = 11;
document.write( LongestSubarray(arr, n, k));
 
</script>

Output

Complexity Analysis:

Time Complexity: O(n * n)
Auxiliary Space: O(n)

An efficient approach is to keep track of the current count in a single traversal. Whenever we find an element whose modulo is not same, we reset count as 0.

Implementation:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to find longest sub-array
// whose elements gives same remainder
// when divided with K
int LongestSubarray(int arr[], int n, int k)
{
    int count = 1;
    int max_length = 1; 
    int prev_mod = arr[0] % k;
   
    // Iterate in the array 
    for (int i = 1; i < n; i++) { 
 
        int curr_mod = arr[i] % k;
   
        // check if array element 
        // greater then X or not 
        if (curr_mod == prev_mod) { 
            count++;
        } 
        else { 
   
            max_length = max(max_length, count);   
            count = 1; 
            prev_mod = curr_mod;
        } 
    } 
     
    return max(max_length, count); 
}
 
// Driver code
int main()
{
    int arr[] = { 4, 9, 7, 18, 29, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 11;
    cout << LongestSubarray(arr, n, k);
    return 0;
}

Java

// Java implementation of above approach 
 
class GFG {
 
// function to find longest sub-array 
// whose elements gives same remainder 
// when divided with K 
    static public int LongestSubarray(int arr[], int n, int k) {
        int count = 1;
        int max_length = 1;
        int prev_mod = arr[0] % k;
 
        // Iterate in the array 
        for (int i = 1; i < n; i++) {
 
            int curr_mod = arr[i] % k;
 
            // check if array element 
            // greater then X or not 
            if (curr_mod == prev_mod) {
                count++;
            } else {
 
                max_length = Math.max(max_length, count);
                count = 1;
                prev_mod = curr_mod;
            }
        }
 
        return Math.max(max_length, count);
    }
 
// Driver code 
    public static void main(String[] args) {
        int arr[] = {4, 9, 7, 18, 29, 11};
        int n = arr.length;
        int k = 11;
        System.out.print(LongestSubarray(arr, n, k));
    }
}
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation of above approach
 
# function to find longest sub-array
# whose elements gives same remainder
#  when divided with K
 
def LongestSubarray(arr,n,k):
    count = 1
    max_lenght = 1
    prev_mod = arr[0]%k
 
    # Iterate in the array
    for i in range(1,n):
        curr_mod = arr[i]%k
 
       #  check if array element 
       # greater then X or not 
        if curr_mod==prev_mod:
            count+=1
        else:
            max_lenght = max(max_lenght,count)
            count=1
            prev_mod = curr_mod
 
 
    return max(max_lenght,count)
 
# Driver code
arr = [4, 9, 7, 18, 29, 11]
n = len(arr)
k =11
print(LongestSubarray(arr,n,k))
 
 
 
# This code is contributed by Shrikant13

C#

// C# implementation of above approach
using System;
 
class GFG
{
     
// function to find longest sub-array
// whose elements gives same remainder
// when divided with K
static int LongestSubarray(int []arr, int n, int k)
{
    int count = 1;
    int max_length = 1; 
    int prev_mod = arr[0] % k;
 
    // Iterate in the array 
    for (int i = 1; i < n; i++)
    { 
 
        int curr_mod = arr[i] % k;
 
        // check if array element 
        // greater then X or not 
        if (curr_mod == prev_mod)
        { 
            count++;
        } 
        else
        { 
            max_length = Math.Max(max_length, count); 
            count = 1; 
            prev_mod = curr_mod;
        } 
    } 
    return Math.Max(max_length, count); 
}
 
// Driver code
public static void Main()
{
    int[] arr = { 4, 9, 7, 18, 29, 11 };
    int n = arr.Length;
    int k = 11;
    Console.Write(LongestSubarray(arr, n, k));
}
}
 
// This code is contributed by Shivi_Aggarwal

PHP

<?php
// PHP implementation of above approach
 
// function to find longest sub-array
// whose elements gives same remainder
// when divided with K
function LongestSubarray($arr, $n, $k)
{
    $cnt = 1;
    $max_length = 1; 
    $prev_mod = $arr[0] % $k;
 
    // Iterate in the array 
    for ($i = 1; $i < $n; $i++) 
    { 
 
        $curr_mod = $arr[$i] % $k;
 
        // check if array element 
        // greater then X or not 
        if ($curr_mod == $prev_mod) 
        { 
            $cnt++;
        } 
        else
        { 
            $max_length = max($max_length, $cnt); 
            $cnt = 1; 
            $prev_mod = $curr_mod;
        } 
    } 
     
    return max($max_length, $cnt);
}
 
// Driver code
$arr = array( 4, 9, 7, 18, 29, 11 );
$n = count($arr) ;
$k = 11;
echo LongestSubarray($arr, $n, $k);
 
// This code is contributed by 29AjayKumar
?>

Javascript

<script>
// Javascript implementation of above approach
     
    // function to find longest sub-array
// whose elements gives same remainder
// when divided with K
    function LongestSubarray(arr,n,k)
    {
        let count = 1;
        let max_length = 1;
        let prev_mod = arr[0] % k;
  
        // Iterate in the array
        for (let i = 1; i < n; i++) {
  
            let curr_mod = arr[i] % k;
  
            // check if array element
            // greater then X or not
            if (curr_mod == prev_mod) {
                count++;
            } else {
  
                max_length = Math.max(max_length, count);
                count = 1;
                prev_mod = curr_mod;
            }
        }
  
        return Math.max(max_length, count);
    }
     
    // Driver code
    let arr = [4, 9, 7, 18, 29, 11];
    let n = arr.length;
    let k = 11;
    document.write(LongestSubarray(arr, n, k));
 
// This code is contributed by rag2127
</script>

Output

Complexity Analysis:

Time Complexity: O(n)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!