Encuentre la fracción coprima más grande menor que la fracción dada

Considere el conjunto de fracciones irreducibles A = {n/d | n≤d y d ≤ 10000 y mcd(n, d) = 1} . Te dan un miembro de este conjunto y tu tarea es encontrar la fracción más grande en este conjunto menor que la fracción dada.

Nota: Este es un conjunto y todos los miembros son únicos.

Ejemplos:

Entrada : n = 1, d = 4
Salida: {2499, 9997}  
Explicación: 2499/9997 es la fracción más grande.

Entrada: n = 2, d = 4
Salida: {4999, 9999}
Explicación : 4999/9999 es la fracción más grande. 

Planteamiento: La solución al problema se basa en el siguiente concepto matemático:

Digamos que la fracción deseada es p/q. Asi que,  

p/q < n/d
p < (n*q)/d
Como queremos que p/q sea menor que n/d, empecemos a iterar sobre q desde q = d+1.
Luego, para cada valor de q, el valor de p será floor((n*q)/d) .  

Siga los pasos a continuación para implementar la idea anterior:

• Cree dos variables num y den para almacenar la respuesta final. Inicialícelos como num =- 1 y den =1 .
• Ahora, bucle i de d+1 a 10000 :
  • Calcula el valor de la fracción con denominador i usando la observación anterior.
  • El numerador será (n*i)/d [esta es una división entera aquí, es decir, da el valor mínimo] y el denominador = i+1
  • Si la fracción es mayor que num/den , actualice num y den en consecuencia.
• Después de todas las iteraciones , num y den almacenarán el numerador y el denominador requeridos.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required fraction
vector<int> numAndDen(int n, int d)
{
    int num = -1, den = 1;
    vector<int> ans;
 
    // Loop to find the fraction
    for (int i = d + 1; i <= 10000; i++) {
        int x = (n * i) / d;
        if (1.0 * x / i > 1.0 * num / den
            and __gcd(x, i) == 1)
            num = x, den = i;
    }
    ans.push_back(num);
    ans.push_back(den);
    return ans;
}
 
// Driver code
int main()
{
    int n = 1, d = 4;
 
    // Function call
    vector<int> ans = numAndDen(n, d);
    for (auto i : ans)
        cout << i << " ";
    return 0;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
    public static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
 
    // Function to find the required fraction
    public static ArrayList<Integer> numAndDen(int n, int d)
    {
        int num = -1;
        int den = 1;
        ArrayList<Integer> ans = new ArrayList<Integer>();
 
        // Loop to find the fraction
        for (int i = d + 1; i <= 10000; i++) {
            int x = (n * i) / d;
            if (1.0 * x / i > 1.0 * num / den
                && gcd(x, i) == 1) {
                num = x;
                den = i;
            }
        }
        ans.add(num);
        ans.add(den);
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 1, d = 4;
 
        // Function call
        ArrayList<Integer> ans = numAndDen(n, d);
        for (Integer i : ans)
            System.out.print(i + " ");
    }
}
 
// This code is contributed by Rohit Pradhan

# Python3 code to implement the approach
 
from math import gcd
 
# Function to find the required fraction
def numAndDen(n, d) :
 
    num = -1; den = 1;
    ans = [];
 
    # Loop to find the fraction
    for i in range(d + 1, 10001) :
        x = (n * i) // d;
        if ((1.0 * x / i) > (1.0 * num / den) and gcd(x, i) == 1) :
            num = x;
            den = i;
             
    ans.append(num);
    ans.append(den);
     
    return ans;
 
# Driver code
if __name__ ==  "__main__" :
 
    n = 1; d = 4;
 
    # Function call
    ans = numAndDen(n, d);
     
    for i in ans:
        print(i,end=" ");
 
    # This code is contributed by AnkThon

// C# code to implement the approach
using System;
using System.Collections;
public class GFG{
  static int gcd(int a, int b)
  {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
 
  // Function to find the required fraction
  static ArrayList numAndDen(int n, int d)
  {
    int num = -1;
    int den = 1;
    ArrayList ans = new ArrayList();
 
    // Loop to find the fraction
    for (int i = d + 1; i <= 10000; i++) {
      int x = (n * i) / d;
      if (1.0 * x / i > 1.0 * num / den
          && gcd(x, i) == 1) {
        num = x;
        den = i;
      }
    }
    ans.Add(num);
    ans.Add(den);
    return ans;
  }
 
  // Driver Code
  static public void Main (){
    int n = 1, d = 4;
 
    // Function call
    ArrayList ans = numAndDen(n, d);
    foreach(var i in ans)
      Console.Write(i + " ");
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
      // JavaScript code for the above approach
      function __gcd(a, b) {
          if (b == 0)
              return a;
          return __gcd(b, a % b);
      }
       
      // Function to find the required fraction
      function numAndDen(n, d) {
          let num = -1, den = 1;
          let ans = [];
 
          // Loop to find the fraction
          for (let i = d + 1; i <= 10000; i++) {
              let x = Math.floor((n * i) / d);
              if (1.0 * (x / i) > 1.0 * (num / den)
                  && __gcd(x, i) == 1)
                  num = x, den = i;
          }
          ans.push(num);
          ans.push(den);
          return ans;
      }
 
      // Driver code
      let n = 1, d = 4;
 
      // Function call
      let ans = numAndDen(n, d);
      for (let i of ans)
          document.write(i + " ");
 
  // This code is contributed by Potta Lokesh
  </script>

2499 9997 

Complejidad temporal: O(n)
Espacio auxiliar: O(1)