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.
Constraints
0 ≤ a, b ≤ 10¹⁸
Examples
Example 1
Input:
a = 48
b = 18
Expected output:
expected = 6Input:
long long a = 48;
long long b = 18;
Expected output:
long long expected = 6;Input:
long a = 48;
long b = 18;
Expected output:
long expected = 6;Explanation
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the answer is 6.
Example 2
Input:
a = 17
b = 5
Expected output:
expected = 1Input:
long long a = 17;
long long b = 5;
Expected output:
long long expected = 1;Input:
long a = 17;
long b = 5;
Expected output:
long expected = 1;Explanation
17 and 5 share no factor other than 1.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
The gcd does not change when you replace a pair with the remainder step.
Hint 2
Keep swapping the roles of the two numbers until the second becomes zero.
Hint 3
Be sure to handle the case where both inputs are zero.
Expected complexity
O(log min(a, b)) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.