Minimum gcd operations to make all array elements one | Java program to find 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
import java . util . * ; class GFG { static int __gcd ( int a , int b ) { if ( a == 0 ) return b ; return __gcd ( b % a , a ) ; } static int minimumMoves ( int A [ ] , int N ) { int one = 0 ; for ( int i = 0 ; i < N ; i ++ ) if ( A [ i ] == 1 ) one ++ ; if ( one != 0 ) return N - one ; int minimum = Integer . MAX_VALUE ; for ( int i = 0 ; i < N ; i ++ ) { int g = A [ i ] ; for ( int j = i + 1 ; j < N ; j ++ ) { g = __gcd ( A [ j ] , g ) ; if ( g == 1 ) { minimum = Math . min ( minimum , j - i ) ; break ; } } } if ( minimum == Integer . MAX_VALUE ) return - 1 ; else return N + minimum - 1 ; } public static void main ( String [ ] args ) { int A [ ] = { 2 , 4 , 3 , 9 } ; int N = A . length ; System . out . print ( minimumMoves ( A , N ) ) ; } }