Problem
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.
Einschränkungen
0 ≤ a, b ≤ 10¹⁸
Beispiele
Beispiel 1
Eingabe:
a = 48
b = 18
Erwartete Ausgabe:
expected = 6Eingabe:
long long a = 48;
long long b = 18;
Erwartete Ausgabe:
long long expected = 6;Eingabe:
long a = 48;
long b = 18;
Erwartete Ausgabe:
long expected = 6;Erläuterung
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the answer is 6.
Beispiel 2
Eingabe:
a = 17
b = 5
Erwartete Ausgabe:
expected = 1Eingabe:
long long a = 17;
long long b = 5;
Erwartete Ausgabe:
long long expected = 1;Eingabe:
long a = 17;
long b = 5;
Erwartete Ausgabe:
long expected = 1;Erläuterung
17 and 5 share no factor other than 1.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
The gcd does not change when you replace a pair with the remainder step.
Hinweis 2
Keep swapping the roles of the two numbers until the second becomes zero.
Hinweis 3
Be sure to handle the case where both inputs are zero.
Erwartete Komplexität
O(log min(a, b)) time, O(1) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.