Minimize Array length by repeatedly replacing co | Recursive function to return gcd of a and b ; Function to find the final array length by replacing coprime pair with 1 ; Iterate over all pairs of element ; Check if gcd is 1 ; If no coprime pair found return false ; Driver code ; Check if atleast one coprime pair exists in the array ; If no such pair exists
function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } function hasCoprimePair ( arr , n ) { for ( i = 0 ; i < n - 1 ; i ++ ) { for ( j = i + 1 ; j < n ; j ++ ) { if ( ( __gcd ( arr [ i ] , arr [ j ] ) ) == 1 ) { return true ; } } } return false ; } var n = 3 ; var arr = [ 6 , 9 , 15 ] ; if ( hasCoprimePair ( arr , n ) ) { document . write ( 1 + " " ) ; } else { document . write ( n + " " ) ; }