Problème
Return the greatest common divisor of a and b. Euclid's algorithm repeatedly replaces (a, b) with (b, a mod b) until b is 0.
Implement gcd(a, b).
Input
a: The first number. b: The second number.
Output
Return gcd(a, b). gcd(0, 0) is 0.
Contraintes
0 ≤ a, b ≤ 10¹⁸
Exemples
Exemple 1
Entrée :
a = 48
b = 18
Sortie attendue :
expected = 6Entrée :
long long a = 48;
long long b = 18;
Sortie attendue :
long long expected = 6;Entrée :
long a = 48;
long b = 18;
Sortie attendue :
long expected = 6;Explication
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the answer is 6.
Exemple 2
Entrée :
a = 17
b = 5
Sortie attendue :
expected = 1Entrée :
long long a = 17;
long long b = 5;
Sortie attendue :
long long expected = 1;Entrée :
long a = 17;
long b = 5;
Sortie attendue :
long expected = 1;Explication
17 and 5 share no factor other than 1.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
The gcd does not change when you replace a pair with the remainder step.
Indice 2
Keep swapping the roles of the two numbers until the second becomes zero.
Indice 3
Be sure to handle the case where both inputs are zero.
Complexité attendue
O(log min(a, b)) time, O(1) extra space
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.