text: Minimize Array length by repeatedly replacing co | C ++ Program for the above approach ; Function to find the final array length by replacing coprime pair with 1 ; Iterate over all pairs of element ; Check if gcd is 1 ; If no coprime pair found return false ; Driver code ; Check if atleast one coprime pair exists in the array ; If no such pair exists
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; bool hasCoprimePair ( vector < int > & arr , int n ) { for ( int i = 0 ; i < n - 1 ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( __gcd ( arr [ i ] , arr [ j ] ) == 1 ) { return true ; } } } return false ; } int main ( ) { int n = 3 ; vector < int > arr = { 6 , 9 , 15 } ; if ( hasCoprimePair ( arr , n ) ) { cout << 1 << endl ; } else { cout << n << endl ; } }