Estaba practicando para un desafío de codificación y me encontré con este problema.
A y su amigo compraron un número cada uno en la tienda de números enteros, A tiene el número N y su amigo tiene el número M. A quiere que ambos números sean coprimos. Para lograr esto, A divide ambos números por el número más grande que puede dividir a ambos números. A quiere saber la suma de números después de hacer esta operación, ayúdalo a encontrar esa suma.
Aporte
Input: N = 6, M = 5 Output: 11 Explanation: The largest number that can divide both 5 and 6 is 1. After dividing, 5+6 = 11.He probado este código
long sum(long N, long M){ long divider = 1; long min = Math.min(N,M); for(long i=2; i<=min; i++) if(N%i==0 && M%i==0) divider=i; return (N/divider) + (M/divider); }Pero la complejidad esperada en tiempo de ejecución es O(log(n)). Pero mi código da O(n).
No puedo encontrar ningún método para hacerlo logarítmico. Por favor, ayúdame. 😀😀
Debe usar cualquier algoritmo eficiente para encontrar el MCD - Máximo común divisor . Por ejemplo, puede probar el algoritmo euclidiano con una complejidad de tiempo O(log(min(N, M)) .
public static long sum(long N, long M) { long gcd = gcdEuclideanAlgorithm(N, M); return (N / gcd) + (M / gcd); } private static long gcdEuclideanAlgorithm(long a, long b) { return b == 0 ? a : gcdEuclideanAlgorithm(b, a % b); }Puedes encontrar más algoritmos aquí .