Minimum gcd operations to make all array elements one | __gcd function ; Function to count number of moves . ; Counting Number of ones . ; If there is a one ; Find smallest subarray with GCD equals to one . ; to calculate GCD ; Not Possible ; Final answer ; Driver program
def __gcd ( a , b ) : NEW_LINE INDENT if ( a == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT return __gcd ( b % a , a ) NEW_LINE DEDENT def minimumMoves ( A , N ) : NEW_LINE INDENT one = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( A [ i ] == 1 ) : NEW_LINE INDENT one += 1 NEW_LINE DEDENT DEDENT if ( one != 0 ) : NEW_LINE INDENT return N - one NEW_LINE DEDENT minimum = + 2147483647 NEW_LINE for i in range ( N ) : NEW_LINE INDENT g = A [ i ] NEW_LINE for j in range ( i + 1 , N ) : NEW_LINE INDENT g = __gcd ( A [ j ] , g ) NEW_LINE if ( g == 1 ) : NEW_LINE INDENT minimum = min ( minimum , j - i ) NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT if ( minimum == + 2147483647 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return N + minimum - 1 ; NEW_LINE DEDENT DEDENT A = [ 2 , 4 , 3 , 9 ] NEW_LINE N = len ( A ) NEW_LINE print ( minimumMoves ( A , N ) ) NEW_LINE