Đề bài
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.
Ràng buộc
0 ≤ a, b ≤ 10¹⁸
Ví dụ
Ví dụ 1
Đầu vào:
a = 48
b = 18
Kết quả mong đợi:
expected = 6Đầu vào:
long long a = 48;
long long b = 18;
Kết quả mong đợi:
long long expected = 6;Đầu vào:
long a = 48;
long b = 18;
Kết quả mong đợi:
long expected = 6;Giải thích
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the answer is 6.
Ví dụ 2
Đầu vào:
a = 17
b = 5
Kết quả mong đợi:
expected = 1Đầu vào:
long long a = 17;
long long b = 5;
Kết quả mong đợi:
long long expected = 1;Đầu vào:
long a = 17;
long b = 5;
Kết quả mong đợi:
long expected = 1;Giải thích
17 and 5 share no factor other than 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
The gcd does not change when you replace a pair with the remainder step.
Gợi ý 2
Keep swapping the roles of the two numbers until the second becomes zero.
Gợi ý 3
Be sure to handle the case where both inputs are zero.
Độ phức tạp mong đợi
O(log min(a, b)) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.