Pair of integers having least GCD among all given pairs having GCD exceeding K | Java 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
import java . util . * ; class GFG { static int GCD ( int a , int b ) { if ( b == 0 ) { return a ; } return GCD ( b , a % b ) ; } static void GcdPair ( int [ ] [ ] arr , int k ) { int lo = 0 , hi = arr . length - 1 , mid ; int [ ] ans = { - 1 , 0 } ; while ( lo <= hi ) { mid = lo + ( hi - lo ) / 2 ; if ( GCD ( arr [ mid ] [ 0 ] , arr [ mid ] [ 1 ] ) > k ) { ans = arr [ mid ] ; hi = mid - 1 ; } else lo = mid + 1 ; } if ( ans [ 0 ] == - 1 ) System . out . print ( " - 1" ) ; else System . out . print ( " ( ▁ " + ans [ 0 ] + " , ▁ " + ans [ 1 ] + " ▁ ) " ) ; return ; } public static void main ( String [ ] args ) { int [ ] [ ] arr = { { 3 , 6 } , { 15 , 30 } , { 25 , 75 } , { 30 , 120 } } ; int K = 16 ; GcdPair ( arr , K ) ; } }