Greatest Common Divisor via Euclidean Recursion

Medium ⏱ 12 min 45% acceptance ★★★★★ 4.6
Implement gcd(a, b) computing the greatest common divisor of two non-negative integers using the recursive Euclidean algorithm: gcd(a, 0) = a, and gcd(a, b) = gcd(b, a % b) otherwise.

Examples

Example 1
Input
gcd(48, 18)
Output
6
Explanation

48 = 2*18 + 12 -> gcd(18,12) -> gcd(12,6) -> gcd(6,0) = 6.

Example 2
Input
gcd(17, 5)
Output
1
Explanation

17 and 5 are coprime.

Constraints

  • a >= 0, b >= 0, not both zero.

Topics

RecursionMath

Companies

AmazonGoldman SachsDeutsche Bank

Hints

Hint 1

Base case: b == 0, return a.

Hint 2

Recursive case: gcd(b, a % b).

← Integer Power Function (Recursive) Sum a List Recursively →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.