Greatest Common Divisor

Difficulty: Easy · Topic: Math for algorithms

Return the greatest common divisor of non-negative integers a and b. Euclid's insight: any common divisor of a and b also divides a mod b, so gcd(a, b) = gcd(b, a mod b), and gcd(x, 0) = x.

Examples

gcd(48, 18)
→ 6

48 = 2·18 + 12, 18 = 1·12 + 6, 12 = 2·6 + 0.

gcd(7, 5)
→ 1

Target complexity: time O(log min(a,b)), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.