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 Kint 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 codeint 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 approachimport java .io.*;class GFG{// function to find longest sub-array// whose elements gives same remainder// when divided with Kstatic 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 codepublic 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 Kdef 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 codeif __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 approachusing System;class GFG{// function to find longest sub-array// whose elements gives same remainder// when divided with Kstatic 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 codepublic 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 Kfunction 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 Kfunction 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 codevar arr = [4, 9, 7, 18, 29, 11 ];var n = arr.length;var k = 11;document.write( LongestSubarray(arr, n, k));</script> |
Output
3
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 Kint 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 codeint 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 Kdef 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 codearr = [4, 9, 7, 18, 29, 11]n = len(arr)k =11print(LongestSubarray(arr,n,k))# This code is contributed by Shrikant13 |
C#
// C# implementation of above approachusing System;class GFG{ // function to find longest sub-array// whose elements gives same remainder// when divided with Kstatic 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 codepublic 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 Kfunction 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
3
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
