문제
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.
제약 조건
0 ≤ a, b ≤ 10¹⁸
예시
예시 1
입력:
a = 48
b = 18
예상 출력:
expected = 6입력:
long long a = 48;
long long b = 18;
예상 출력:
long long expected = 6;입력:
long a = 48;
long b = 18;
예상 출력:
long expected = 6;설명
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the answer is 6.
예시 2
입력:
a = 17
b = 5
예상 출력:
expected = 1입력:
long long a = 17;
long long b = 5;
예상 출력:
long long expected = 1;입력:
long a = 17;
long b = 5;
예상 출력:
long expected = 1;설명
17 and 5 share no factor other than 1.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
The gcd does not change when you replace a pair with the remainder step.
힌트 2
Keep swapping the roles of the two numbers until the second becomes zero.
힌트 3
Be sure to handle the case where both inputs are zero.
예상 복잡도
O(log min(a, b)) time, O(1) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.