Check if all array elements can be reduced to less than X | Java Program to implement the above approach ; Function to check if all array elements can be reduced to less than X or not ; Checks if all array elements are already a X or not ; Traverse every possible pair ; Calculate GCD of two array elements ; If gcd is a 1 ; If gcd is a X , then a pair is present to reduce all array elements to a X ; If no pair is present with gcd is a X ; Function to check if all array elements area X ; Function to calculate gcd of two numbers ; Driver Code
import java . io . * ; import java . util . Arrays ; class GFG { public static boolean findAns ( int [ ] A , int N , int X ) { if ( check ( A , X ) ) { return true ; } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = i + 1 ; j < N ; j ++ ) { int gcd = gcd ( A [ i ] , A [ j ] ) ; if ( gcd != 1 ) { if ( gcd <= X ) { return true ; } } } } return false ; } public static boolean check ( int [ ] A , int X ) { for ( int i = 0 ; i < A . length ; i ++ ) { if ( A [ i ] > X ) { return false ; } } return true ; } public static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } public static void main ( String [ ] args ) { int X = 4 ; int [ ] A = { 2 , 1 , 5 , 3 , 6 } ; int N = 5 ; System . out . println ( findAns ( A , N , X ) ) ; } }