Pair of integers having least GCD among all given pairs having GCD exceeding K | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int GCD ( int a , int b ) { if ( b == 0 ) { return a ; } return GCD ( b , a % b ) ; } void GcdPair ( vector < pair < int , int > > arr , int k ) { int lo = 0 , hi = arr . size ( ) - 1 , mid ; pair < int , int > ans ; ans = make_pair ( -1 , 0 ) ; while ( lo <= hi ) { mid = lo + ( hi - lo ) / 2 ; if ( GCD ( arr [ mid ] . first , arr [ mid ] . second ) > k ) { ans = arr [ mid ] ; hi = mid - 1 ; } else lo = mid + 1 ; } if ( ans . first == -1 ) cout << " - 1" ; else cout << " ( ▁ " << ans . first << " , ▁ " << ans . second << " ▁ ) " ; return ; } int main ( ) { vector < pair < int , int > > arr = { { 3 , 6 } , { 15 , 30 } , { 25 , 75 } , { 30 , 120 } } ; int K = 16 ; GcdPair ( arr , K ) ; return 0 ; }