Minimum gcd operations to make all array elements one | CPP program to find minimum GCD operations to make all array elements one . ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 = INT_MAX ; 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 = min ( minimum , j - i ) ; break ; } } } if ( minimum == INT_MAX ) return -1 ; else return N + minimum - 1 ; } int main ( ) { int A [ ] = { 2 , 4 , 3 , 9 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << minimumMoves ( A , N ) ; return 0 ; }