Par de enteros que tienen el menor GCD entre todos los pares dados que tienen un GCD superior a K

Dada una array arr[][] que contiene pares de enteros en orden creciente de GCD y un entero K , la tarea es encontrar un par de enteros cuyo GCD sea al menos K y también sea el menor entre todos los GCD posibles que excedan K . Si no existe tal par, imprima -1 .
Ejemplos:

Entrada: arr[][] = [(3, 6), (15, 30), (25, 75), (30, 120)], K = 16 
Salida: (25, 75) 
Explicación: 
El GCD de ( 25, 75) es 25 que es mayor que 16 y menor entre todos los MCD posibles.

Entrada: arr[] = [(2, 5), (12, 36), (13, 26)], K = 14 
Salida: -1

Enfoque ingenuo: el enfoque más simple es iterar sobre todos los pares de la array dada y verificar cada par, si su GCD excede K . De todos esos pares, imprima el par que tenga el menor GCD .

Complejidad de tiempo: O(N * log(N)) 
Espacio auxiliar: O(1)

Enfoque eficiente: la idea es observar que los elementos de la array se ordenan en orden creciente de sus valores de GCD del par, así que use la búsqueda binaria . Siga los pasos a continuación para resolver el problema:

• Calcule el valor medio del espacio de búsqueda y verifique si GCD de arr[mid] > K .
• Si supera K , actualice la respuesta y reduzca el valor superior del espacio de búsqueda a la mitad de – 1 .
• Si el GCD de arr[mid] ≤ K , aumente el valor inferior del espacio de búsqueda a mid + 1 .
• Continúe el proceso anterior hasta que el valor inferior sea menor o igual que el valor superior.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// the GCD of two numbers
int GCD(int a, int b)
{
    if (b == 0) {
        return a;
    }
    return GCD(b, a % b);
}
 
// Function to print the pair
// having a gcd value just greater
// than the given integer
void GcdPair(vector<pair<int, int> > arr, int k)
{
    // Initialize variables
    int lo = 0, hi = arr.size() - 1, mid;
    pair<int, int> ans;
    ans = make_pair(-1, 0);
 
    // Iterate until low less
    // than equal to high
    while (lo <= hi) {
 
        // Calculate mid
        mid = lo + (hi - lo) / 2;
        if (GCD(arr[mid].first,
                arr[mid].second)
            > k) {
            ans = arr[mid];
            hi = mid - 1;
        }
        // Reducing the search space
        else
            lo = mid + 1;
    }
 
    // Print the answer
    if (ans.first == -1)
        cout << "-1";
    else
        cout << "( " << ans.first << ", "
             << ans.second << " )";
 
    return;
}
 
// Driver Code
int main()
{
    // Given array and K
    vector<pair<int, int> > arr = { { 3, 6 },
                                    { 15, 30 },
                                    { 25, 75 },
                                    { 30, 120 } };
    int K = 16;
 
    // Function Call
    GcdPair(arr, K);
 
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to calculate
// the GCD of two numbers
static int GCD(int a, int b)
{
  if (b == 0)
  {
    return a;
  }
  return GCD(b, a % b);
}
 
// Function to print the pair
// having a gcd value just
// greater than the given integer
static void GcdPair(int [][]arr,
                    int k)
{
  // Initialize variables
  int lo = 0, hi = arr.length - 1, mid;
  int []ans = {-1, 0};
 
  // Iterate until low less
  // than equal to high
  while (lo <= hi)
  {
    // Calculate mid
    mid = lo + (hi - lo) / 2;
    if (GCD(arr[mid][0],
            arr[mid][1]) > k)
    {
      ans = arr[mid];
      hi = mid - 1;
    }
     
    // Reducing the search space
    else
      lo = mid + 1;
  }
 
  // Print the answer
  if (ans[0] == -1)
    System.out.print("-1");
  else
    System.out.print("( " + ans[0] +
                     ", " + ans[1] + " )");
  return;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array and K
  int [][]arr = {{3, 6},
                 {15, 30},
                 {25, 75},
                 {30, 120}};
  int K = 16;
 
  // Function Call
  GcdPair(arr, K);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for the above approach
 
# Function to calculate
# the GCD of two numbers
def GCD(a, b):
     
    if (b == 0):
        return a
         
    return GCD(b, a % b)
 
# Function to print the pair
# having a gcd value just greater
# than the given integer
def GcdPair(arr, k):
     
    # Initialize variables
    lo = 0
    hi = len(arr) - 1
    ans = [-1, 0]
 
    # Iterate until low less
    # than equal to high
    while (lo <= hi):
 
        # Calculate mid
        mid = lo + (hi - lo) // 2
        if (GCD(arr[mid][0], arr[mid][1]) > k):
            ans = arr[mid]
            hi = mid - 1
 
        # Reducing the search space
        else:
            lo = mid + 1
 
    # Print the answer
    if (len(ans) == -1):
        print("-1")
    else:
        print("(", ans[0], ",", ans[1], ")")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array and K
    arr = [ [ 3, 6 ],
            [ 15, 30 ],
            [ 25, 75 ],
            [ 30, 120 ] ]
    K = 16
 
    # Function call
    GcdPair(arr, K)
 
# This code is contributed by mohit kumar 29

// C# program for
// the above approach
using System;
class GFG{
 
// Function to calculate
// the GCD of two numbers
static int GCD(int a, int b)
{
  if (b == 0)
  {
    return a;
  }
  return GCD(b, a % b);
}
 
// Function to print the pair
// having a gcd value just
// greater than the given integer
static void GcdPair(int [,]arr,
                    int k)
{
  // Initialize variables
  int lo = 0, hi = arr.Length - 1, mid;
  int []ans = {-1, 0};
 
  // Iterate until low less
  // than equal to high
  while (lo <= hi)
  {
    // Calculate mid
    mid = lo + (hi - lo) / 2;
    if (GCD(arr[mid, 0],
            arr[mid, 1]) > k)
    {
      ans = GetRow(arr, mid);
      hi = mid - 1;
    }
 
    // Reducing the search space
    else
      lo = mid + 1;
  }
 
  // Print the answer
  if (ans[0] == -1)
    Console.Write("-1");
  else
    Console.Write("( " + ans[0] +
                  ", " + ans[1] + " )");
  return;
}
 
public static int[] GetRow(int[,] matrix, int row)
{
  var rowLength = matrix.GetLength(1);
  var rowVector = new int[rowLength];
 
  for (var i = 0; i < rowLength; i++)
    rowVector[i] = matrix[row, i];
 
  return rowVector;
}
   
// Driver Code
public static void Main(String[] args)
{
  // Given array and K
  int [,]arr = {{3, 6},
                {15, 30},
                {25, 75},
                {30, 120}};
  int K = 16;
 
  // Function Call
  GcdPair(arr, K);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program for
// the above approach
 
    // Function to calculate
    // the GCD of two numbers
    function GCD(a , b) {
        if (b == 0) {
            return a;
        }
        return GCD(b, a % b);
    }
 
    // Function to print the pair
    // having a gcd value just
    // greater than the given integer
    function GcdPair(arr , k) {
        // Initialize variables
        var lo = 0, hi = arr.length - 1, mid;
        var ans = [ -1, 0 ];
 
        // Iterate until low less
        // than equal to high
        while (lo <= hi) {
            // Calculate mid
            mid = lo + parseInt((hi - lo) / 2);
            if (GCD(arr[mid][0], arr[mid][1]) > k) {
                ans = arr[mid];
                hi = mid - 1;
            }
 
            // Reducing the search space
            else
                lo = mid + 1;
        }
 
        // Print the answer
        if (ans[0] == -1)
            document.write("-1");
        else
            document.write("( " + ans[0] + ", " + ans[1] + " )");
        return;
    }
 
    // Driver Code
     
        // Given array and K
        var arr = [ [ 3, 6 ], [ 15, 30 ], [ 25, 75 ], [ 30, 120 ] ];
        var K = 16;
 
        // Function Call
        GcdPair(arr, K);
 
// This code is contributed by todaysgaurav
 
</script>

( 25, 75 )

Complejidad de tiempo: O(log(N) ² ) 
Espacio auxiliar: O(1)