698. GCD of Two Numbers (Euclidean Algorithm)

Given two non-negative integers a and b, compute their GCD (Greatest Common Divisor) using the recursive Euclidean algorithm. The Euclidean algorithm states: GCD(a, 0) = a and GCD(a, b) = GCD(b, a % b). Return the GCD.

Input: Two non-negative integers a and b (0 ≤ a, b ≤ 10^9), separated by a comma.

Output: A single integer — the GCD of a and b.

Examples

Input: 48, 18
Output: 6
Explanation: GCD(48,18): GCD(18,12)→GCD(12,6)→GCD(6,0)=6.

Input: 7, 0
Output: 7
Explanation: GCD(7, 0) = 7 by base case.

Input: 100, 75
Output: 25
Explanation: GCD(100,75)→GCD(75,25)→GCD(25,0)=25.

Constraints

• 0 <= a, b <= 10^9

Asked by