Length of longest subarray of length at least 2 with maximum GCD | C ++ program for the above approach ; Function to calculate GCD of two numbers ; Function to find maximum size subarray having maximum GCD ; Base Case ; Let the maximum GCD be 1 initially ; Loop thourgh array to find maximum GCD of subarray with size 2 ; Traverse the array ; Is a multiple of k , increase cnt ; Else update maximum length with consecutive element divisible by k Set cnt to 0 ; Update the maxLength ; Return the maxLength ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } int maximumGcdSubarray ( int arr [ ] , int n ) { if ( n == 1 ) return 0 ; int k = 1 ; for ( int i = 1 ; i < n ; ++ i ) { k = max ( k , gcd ( arr [ i ] , arr [ i - 1 ] ) ) ; } int cnt = 0 ; int maxLength = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] % k == 0 ) { cnt ++ ; } else { maxLength = max ( maxLength , cnt ) ; cnt = 0 ; } } maxLength = max ( maxLength , cnt ) ; return maxLength ; } int main ( ) { int arr [ ] = { 18 , 3 , 6 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximumGcdSubarray ( arr , n ) ; return 0 ; }