Check if all array elements can be reduced to less than X | C ++ 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 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool findAns ( int A [ ] , int N , int X ) { if ( check ( A , X , N ) ) { return true ; } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = i + 1 ; j < N ; j ++ ) { int g = __gcd ( A [ i ] , A [ j ] ) ; if ( g != 1 ) { if ( g <= X ) { return true ; } } } } return false ; } bool check ( int A [ ] , int X , int N ) { for ( int i = 0 ; i < N ; i ++ ) { if ( A [ i ] > X ) { return false ; } } return true ; } int main ( ) { int X = 4 ; int A [ ] = { 2 , 1 , 5 , 3 , 6 } ; int N = 5 ; if ( findAns ( A , N , X ) ) { cout << " true " ; } else { cout << " false " ; } }