Minimize Array length by repeatedly replacing co | Java Program for the above approach ; Recursive function to return gcd of a and b ; 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
import java . util . * ; class GFG { static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } static boolean hasCoprimePair ( 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 ; } public static void main ( String [ ] args ) { int n = 3 ; int [ ] arr = { 6 , 9 , 15 } ; if ( hasCoprimePair ( arr , n ) ) { System . out . print ( 1 + "NEW_LINE"); } else { System . out . print ( n + "NEW_LINE"); } } }