Maximum possible GCD after replacing at most one element in the given array | Javascript implementation of the approach ; Function to return the maximum possible gcd after replacing a single element ; Prefix and Suffix arrays ; Single state dynamic programming relation for storing gcd of first i elements from the left in Prefix [ i ] ; Initializing Suffix array ; Single state dynamic programming relation for storing gcd of all the elements having index greater than or equal to i in Suffix [ i ] ; If first or last element of the array has to be replaced ; If any other element is replaced ; Return the maximized gcd ; Driver code
function gcd ( a , b ) { if ( b == 0 ) { return a ; } return gcd ( b , a % b ) ; } function MaxGCD ( a , n ) { var Prefix = Array ( n + 2 ) . fill ( 0 ) ; var Suffix = Array ( n + 2 ) . fill ( 0 ) ; var i ; Prefix [ 1 ] = a [ 0 ] ; for ( i = 2 ; i <= n ; i ++ ) { Prefix [ i ] = gcd ( Prefix [ i - 1 ] , a [ i - 1 ] ) ; } Suffix [ n ] = a [ n - 1 ] ; for ( i = n - 1 ; i >= 1 ; i -- ) { Suffix [ i ] = gcd ( Suffix [ i + 1 ] , a [ i - 1 ] ) ; } var ans = Math . max ( Suffix [ 2 ] , Prefix [ n - 1 ] ) ; for ( i = 2 ; i < n ; i ++ ) { ans = Math . max ( ans , gcd ( Prefix [ i - 1 ] , Suffix [ i + 1 ] ) ) ; } return ans ; } var a = [ 6 , 7 , 8 ] ; n = a . length ; document . write ( MaxGCD ( a , n ) ) ;