Greatest Common Divisor

Medium · rating 1100 · math, number-theory

Read two positive integers a and b. Print their greatest common divisor.

Constraints: 1 ≤ a, b ≤ 10⁹

Editorial

Greatest Common Divisor is a fundamental number-theory interview problem, solved elegantly by the Euclidean algorithm.

Approach

The GCD of a and b equals the GCD of b and a mod b. Repeatedly replace the pair until the remainder hits 0; the surviving number is the answer.

while b:
    a, b = b, a % b
return a

Why it works

Any common divisor of a and b also divides a mod b, so the set of common divisors is preserved while the numbers shrink rapidly.

Complexity

Time: O(log(min(a, b))). Space: O(1).

Open Greatest Common Divisor in Code Arena →