Length of the Smallest Subarray that must be removed in order to Maximise the GCD | C ++ program to find the length of the smallest subarray that must be removed in order to maximise the GCD ; Function to find the length of the smallest subarray that must be removed in order to maximise the GCD ; Store the maximum possible GCD of the resulting subarray ; Two pointers initially pointing to the first and last element respectively ; Moving the left pointer to the right if the elements are divisible by the maximum GCD ; Moving the right pointer to the left if the elements are divisible by the maximum GCD ; Return the length of the subarray ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int GetMinSubarrayLength ( int a [ ] , int n ) { int ans = max ( a [ 0 ] , a [ n - 1 ] ) ; int lo = 0 , hi = n - 1 ; while ( lo < n and a [ lo ] % ans == 0 ) lo ++ ; while ( hi > lo and a [ hi ] % ans == 0 ) hi -- ; return ( hi - lo + 1 ) ; } int main ( ) { int arr [ ] = { 4 , 8 , 2 , 1 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int length = GetMinSubarrayLength ( arr , N ) ; cout << length << " STRNEWLINE " ; return 0 ; }