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=2
Output : 4Input : arr[] = { 3, 11, 22, 32, 55, 100, 1, 5}, k=5
Output : 2
Approach:
- Initialize two variables current_count and max_count with value 0;
- Iterate the array from left to right and check the divisibility of each element by k.
- If the element is divisible, then increment current_count, otherwise make current_count equal to 0
- Compare current_count with max_count at each element, if current_count is greater than max_count, assign the value of current_count to max_count
- Finally, output value of max_count
Below is the implementation of the above approach:
C++
// C++ program of above approach #include <bits/stdc++.h> using namespace std; // function to find longest subarray int longestsubarray( int arr[], int n, int k) { int current_count = 0; // this will contain length of longest subarray found int max_count = 0; for ( int i = 0; i < n; i++) { if (arr[i] % k == 0) current_count++; else current_count = 0; max_count = max(current_count, max_count); } return max_count; } // Driver code int main() { int arr[] = { 2, 5, 11, 32, 64, 88 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 8; cout << longestsubarray(arr, n, k); return 0; } |
Java
// Java program of above approach import java.io.*; class GFG { // function to find longest subarray static int longestsubarray( int arr[], int n, int k) { int current_count = 0 ; // this will contain length of // longest subarray found int max_count = 0 ; for ( int i = 0 ; i < n; i++) { if (arr[i] % k == 0 ) current_count++; else current_count = 0 ; max_count = Math.max(current_count, max_count); } return max_count; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 5 , 11 , 32 , 64 , 88 }; int n = arr.length; int k = 8 ; System.out.println(longestsubarray(arr, n, k)); } } // This code is contributed // by ajit |
Python3
# Python 3 program of above approach # function to find longest subarray def longestsubarray(arr, n, k): current_count = 0 # this will contain length of # longest subarray found max_count = 0 for i in range ( 0 , n, 1 ): if (arr[i] % k = = 0 ): current_count + = 1 else : current_count = 0 max_count = max (current_count, max_count) return max_count # Driver code if __name__ = = '__main__' : arr = [ 2 , 5 , 11 , 32 , 64 , 88 ] n = len (arr) k = 8 print (longestsubarray(arr, n, k)) # This code is contributed by # Surendra_Gangwar |
C#
// C# program of above approach using System; class GFG { // function to find longest subarray static int longestsubarray( int [] arr, int n, int k) { int current_count = 0; // this will contain length of // longest subarray found int max_count = 0; for ( int i = 0; i < n; i++) { if (arr[i] % k == 0) current_count++; else current_count = 0; max_count = Math.Max(current_count, max_count); } return max_count; } // Driver code public static void Main() { int [] arr = { 2, 5, 11, 32, 64, 88 }; int n = arr.Length; int k = 8; Console.Write(longestsubarray(arr, n, k)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP program of above approach // function to find longest subarray function longestsubarray( $arr , $n , $k ) { $current_count = 0; // This will contain length of // longest subarray found $max_count = 0; for ( $i = 0; $i < $n ; $i ++) { if ( $arr [ $i ] % $k == 0) $current_count ++; else $current_count = 0; $max_count = max( $current_count , $max_count ); } return $max_count ; } // Driver code $arr = array (2, 5, 11, 32, 64, 88 ); $n = sizeof( $arr ); $k = 8; echo longestsubarray( $arr , $n , $k ); // This code is contributed // by Sach_Code ?> |
Javascript
<script> // Javascript program of above approach // function to find longest subarray function longestsubarray(arr, n, k) { let current_count = 0; // this will contain length of longest subarray found let max_count = 0; for (let i = 0; i < n; i++) { if (arr[i] % k == 0) current_count++; else current_count = 0; max_count = Math.max(current_count, max_count); } return max_count; } let arr = [ 2, 5, 11, 32, 64, 88 ]; let n = arr.length; let k = 8; document.write(longestsubarray(arr, n, k)); </script> |
3
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!