Check if all array elements can be reduced to less than X | 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
def findAns ( A , N , X ) : NEW_LINE INDENT if ( check ( A , X ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( i + 1 , N ) : NEW_LINE gcd = GCD ( A [ i ] , A [ j ] ) NEW_LINE if ( gcd != 1 ) : NEW_LINE INDENT if ( gcd <= X ) : NEW_LINE return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def check ( A , X ) : NEW_LINE INDENT for i in range ( len ( A ) ) : NEW_LINE INDENT if ( A [ i ] > X ) : NEW_LINE return False NEW_LINE DEDENT return True NEW_LINE DEDENT def GCD ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return GCD ( b , a % b ) NEW_LINE DEDENT X = 4 NEW_LINE A = [ 2 , 1 , 5 , 3 , 6 ] NEW_LINE N = 5 NEW_LINE print ( findAns ( A , N , X ) ) NEW_LINE