Problema
Devuelve el máximo común divisor de a y b. El algoritmo de Euclides reemplaza repetidamente (a, b) por (b, a mod b) hasta que b es 0.
Implementa gcd(a, b).
Entrada
a: El primer número. b: El segundo número.
Salida
Devuelve gcd(a, b). gcd(0, 0) es 0.
Restricciones
0 ≤ a, b ≤ 10¹⁸
Ejemplos
Entrada:
a = 48
b = 18
Salida esperada:
expected = 6Entrada:
long long a = 48;
long long b = 18;
Salida esperada:
long long expected = 6;Entrada:
long a = 48;
long b = 18;
Salida esperada:
long expected = 6;Explicación
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, así que la respuesta es 6.
Entrada:
a = 17
b = 5
Salida esperada:
expected = 1Entrada:
long long a = 17;
long long b = 5;
Salida esperada:
long long expected = 1;Entrada:
long a = 17;
long b = 5;
Salida esperada:
long expected = 1;Explicación
17 y 5 no comparten ningún factor aparte de 1.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
El gcd no cambia cuando reemplazas un par con el paso del resto.
Pista 2
Ve intercambiando los roles de los dos números hasta que el segundo sea cero.
Pista 3
Asegúrate de manejar el caso en que ambas entradas sean cero.
Complejidad esperada
tiempo O(log min(a, b)), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.