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++
#include <bits/stdc++.h>
using namespace std;
int LongestSubarray( int arr[], int n, int k)
{
int arr2[n];
for ( int i = 0; i < n; i++)
arr2[i] = arr[i] % k;
int current_length, max_length = 0;
int j;
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;
}
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
import java .io.*;
class GFG
{
static int LongestSubarray( int [] arr,
int n, int 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;
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;
}
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));
}
}
|
Python 3
def LongestSubarray(arr, n, k):
arr2 = [ 0 ] * n
for i in range ( n):
arr2[i] = arr[i] % k
max_length = 0
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
if __name__ = = "__main__" :
arr = [ 4 , 9 , 7 , 18 , 29 , 11 ]
n = len (arr)
k = 11
print (LongestSubarray(arr, n, k))
|
C#
using System;
class GFG
{
static int LongestSubarray( int [] arr,
int n, int 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;
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;
}
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));
}
}
|
PHP
<?php
function LongestSubarray( $arr , $n , $k )
{
$arr2 [ $n ] = array ();
for ( $i = 0; $i < $n ; $i ++)
$arr2 [ $i ] = $arr [ $i ] % $k ;
$current_length ;
$max_length = 0;
$j ;
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 ;
}
$arr = array ( 4, 9, 7, 18, 29, 11 );
$n = sizeof( $arr );
$k = 11;
echo LongestSubarray( $arr , $n , $k );
?>
|
Javascript
<script>
function LongestSubarray(arr, n, 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;
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;
}
var arr = [4, 9, 7, 18, 29, 11 ];
var n = arr.length;
var k = 11;
document.write( LongestSubarray(arr, n, k));
</script>
|
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++
#include <bits/stdc++.h>
using namespace std;
int LongestSubarray( int arr[], int n, int k)
{
int count = 1;
int max_length = 1;
int prev_mod = arr[0] % k;
for ( int i = 1; i < n; i++) {
int curr_mod = arr[i] % k;
if (curr_mod == prev_mod) {
count++;
}
else {
max_length = max(max_length, count);
count = 1;
prev_mod = curr_mod;
}
}
return max(max_length, count);
}
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
class GFG {
static public int LongestSubarray( int arr[], int n, int k) {
int count = 1 ;
int max_length = 1 ;
int prev_mod = arr[ 0 ] % k;
for ( int i = 1 ; i < n; i++) {
int curr_mod = arr[i] % k;
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);
}
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));
}
}
|
Python3
def LongestSubarray(arr,n,k):
count = 1
max_lenght = 1
prev_mod = arr[ 0 ] % k
for i in range ( 1 ,n):
curr_mod = arr[i] % k
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)
arr = [ 4 , 9 , 7 , 18 , 29 , 11 ]
n = len (arr)
k = 11
print (LongestSubarray(arr,n,k))
|
C#
using System;
class GFG
{
static int LongestSubarray( int []arr, int n, int k)
{
int count = 1;
int max_length = 1;
int prev_mod = arr[0] % k;
for ( int i = 1; i < n; i++)
{
int curr_mod = arr[i] % k;
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);
}
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));
}
}
|
PHP
<?php
function LongestSubarray( $arr , $n , $k )
{
$cnt = 1;
$max_length = 1;
$prev_mod = $arr [0] % $k ;
for ( $i = 1; $i < $n ; $i ++)
{
$curr_mod = $arr [ $i ] % $k ;
if ( $curr_mod == $prev_mod )
{
$cnt ++;
}
else
{
$max_length = max( $max_length , $cnt );
$cnt = 1;
$prev_mod = $curr_mod ;
}
}
return max( $max_length , $cnt );
}
$arr = array ( 4, 9, 7, 18, 29, 11 );
$n = count ( $arr ) ;
$k = 11;
echo LongestSubarray( $arr , $n , $k );
?>
|
Javascript
<script>
function LongestSubarray(arr,n,k)
{
let count = 1;
let max_length = 1;
let prev_mod = arr[0] % k;
for (let i = 1; i < n; i++) {
let curr_mod = arr[i] % k;
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);
}
let arr = [4, 9, 7, 18, 29, 11];
let n = arr.length;
let k = 11;
document.write(LongestSubarray(arr, n, k));
</script>
|
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 neveropen!