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
< ? php function __gcd ( $ a , $ b ) { if ( $ a == 0 ) return $ b ; return __gcd ( $ b % $ a , $ a ) ; } function minimumMoves ( $ A , $ N ) { $ one = 0 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) if ( $ A [ $ i ] == 1 ) $ one ++ ; if ( $ one != 0 ) return $ N - $ one ; $ minimum = PHP_INT_MAX ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { $ g = $ A [ $ i ] ; for ( $ j = $ i + 1 ; $ j < $ N ; $ j ++ ) { $ g = __gcd ( $ A [ $ j ] , $ g ) ; if ( $ g == 1 ) { $ minimum = min ( $ minimum , $ j - $ i ) ; break ; } } } if ( $ minimum == PHP_INT_MAX ) return -1 ; else return $ N + $ minimum - 1 ; } $ A = array ( 2 , 4 , 3 , 9 ) ; $ N = sizeof ( $ A ) ; echo ( minimumMoves ( $ A , $ N ) ) ; ? >