Pair of integers having least GCD among all given pairs having GCD exceeding K | Function to calculate the GCD of two numbers ; Function to print the pair having a gcd value just greater than the given integer ; Initialize variables ; Iterate until low less than equal to high ; Calculate mid ; Reducing the search space ; Print the answer ; Driver Code ; Given array and K ; Function call
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 def GcdPair ( arr , k ) : NEW_LINE INDENT lo = 0 NEW_LINE hi = len ( arr ) - 1 NEW_LINE ans = [ - 1 , 0 ] NEW_LINE while ( lo <= hi ) : NEW_LINE INDENT mid = lo + ( hi - lo ) // 2 NEW_LINE if ( GCD ( arr [ mid ] [ 0 ] , arr [ mid ] [ 1 ] ) > k ) : NEW_LINE INDENT ans = arr [ mid ] NEW_LINE hi = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT lo = mid + 1 NEW_LINE DEDENT DEDENT if ( len ( ans ) == - 1 ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " ( " , ans [ 0 ] , " , " , ans [ 1 ] , " ) " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 3 , 6 ] , [ 15 , 30 ] , [ 25 , 75 ] , [ 30 , 120 ] ] NEW_LINE K = 16 NEW_LINE GcdPair ( arr , K ) NEW_LINE DEDENT