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 code
function __gcd ( a , b ) { if ( a == 0 ) return b ; return __gcd ( b % a , a ) ; } function minimumMoves ( A , N ) { let one = 0 ; for ( let i = 0 ; i < N ; i ++ ) if ( A [ i ] == 1 ) one ++ ; if ( one != 0 ) return N - one ; let minimum = Number . MAX_SAFE_INTEGER ; for ( let i = 0 ; i < N ; i ++ ) { let g = A [ i ] ; for ( let j = i + 1 ; j < N ; j ++ ) { g = __gcd ( A [ j ] , g ) ; if ( g == 1 ) { minimum = Math . min ( minimum , j - i ) ; break ; } } } if ( minimum == Number . MAX_SAFE_INTEGER ) return - 1 ; else return N + minimum - 1 ; } let A = [ 2 , 4 , 3 , 9 ] ; let N = A . length ; document . write ( minimumMoves ( A , N ) ) ;