Minimize Array length by repeatedly replacing co | Python3 program for the above approach ; 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
import math NEW_LINE def hasCoprimePair ( arr , n ) : NEW_LINE INDENT for i in range ( n - 1 ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT if ( math . gcd ( arr [ i ] , arr [ j ] ) == 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 NEW_LINE arr = [ 6 , 9 , 15 ] NEW_LINE if ( hasCoprimePair ( arr , n ) ) : NEW_LINE INDENT print ( 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( n ) NEW_LINE DEDENT DEDENT