What Is the GCD Algorithm? Greatest Common Divisor for Coding Interviews

You learned GCD in seventh grade. Then you learned about GPUs and React and approximately six layers of abstraction, and GCD quietly slipped out of your working memory. It comes back during interviews, usually at the worst possible moment, when you're staring at a problem about repeating events or string patterns and wondering why your brain is suddenly empty.

The naive algorithm runs in O(min(a, b)) time. Euclid's version, from 300 BC, runs in O(log min(a, b)). That gap matters more than most prep material lets on, and GCD shows up in more problem types than you'd expect.

The Definition Is Actually Simple

GCD(a, b) is the largest positive integer that divides both a and b with no remainder.

Example: GCD(48, 18) = 6.

Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
Factors of 18: 1, 2, 3, 6, 9, 18
Common factors: 1, 2, 3, 6
Greatest: 6

A few boundary cases worth knowing cold:

GCD(a, 0) = a for any positive a. Every integer divides zero, so a divides zero and a divides a, making a the largest common divisor.
GCD(a, a) = a. A number is always its own greatest divisor.
GCD(1, n) = 1 for any n. Nothing larger than 1 divides 1.

Two numbers are coprime if GCD(a, b) = 1. They share no prime factors. GCD(9, 16) = 1, so 9 and 16 are coprime. This property matters more in interview problems than most prep material acknowledges.

The Naive Approach, and Why You Don't Want It

The intuitive algorithm: loop downward from min(a, b), return the first number that divides both.

def gcd_naive(a: int, b: int) -> int:
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i
    return 1

This works. It just takes O(min(a, b)) time, which means GCD(999_999_999, 1_000_000_000) loops a billion times before returning 1. Your interviewer will watch this loop and quietly update their hire recommendation.

In practice, most inputs won't hit that worst case. But "mostly fine" is not the answer you want to give during a complexity discussion. Euclid had a better idea, and he had it in 300 BC.

One Substitution Cuts It to O(log n)

The Euclidean algorithm rests on one observation: GCD(a, b) = GCD(b, a mod b).

Here is why. Say d divides both a and b. Write a = b·q + r where r = a mod b. Then r = a − b·q. Since d divides a and d divides b·q, d must also divide their difference, r. So every common divisor of (a, b) is also a common divisor of (b, r). The argument works in reverse too. Therefore GCD(a, b) = GCD(b, a mod b).

The base case is GCD(a, 0) = a. The second argument always strictly decreases because a mod b is strictly less than b. So the sequence terminates.

Trace it on GCD(48, 18):

GCD(48, 18) → GCD(18, 48 mod 18) = GCD(18, 12)
GCD(18, 12) → GCD(12, 18 mod 12) = GCD(12,  6)
GCD(12,  6) → GCD( 6, 12 mod  6) = GCD( 6,  0)
GCD( 6,  0) = 6

Four steps, done. The naive approach would have started at 18 and counted down. Euclid beat your first attempt by 23 centuries.

Use the Iterative Version in Interviews

The recursive implementation mirrors the math directly:

def gcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return gcd(b, a % b)

The iterative version is identical in behavior but uses O(1) space:

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

In TypeScript:

function gcd(a: number, b: number): number {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

In a coding interview, use the iterative version. The recursive one uses O(log min(a, b)) stack frames. For most inputs that is fine, but stating the O(1) space version shows you know both and chose deliberately. That distinction is exactly what separates a score-3 answer from a score-4.

On built-ins: Python 3.5+ has math.gcd(a, b), extended to variadic math.gcd(*args) in 3.9. C++17 added std::gcd in <numeric>. Java has BigInteger.gcd() for large numbers but no built-in for plain ints. JavaScript has nothing; write your own.

Why the Complexity Is O(log min(a, b))

The second argument decreases by at least half every two iterations.

If a ≥ b, then a mod b < b. In the next step, b mod (a mod b). If a mod b < b/2, the quotient b / (a mod b) ≥ 2, so b mod (a mod b) < a mod b < b/2. If a mod b ≥ b/2, then b mod (a mod b) = b − (a mod b) ≤ b/2. Either way, after two steps, the smaller argument is at most half what it was. Total steps: O(log min(a, b)).

The formal version is Lamé's theorem (1844): the number of steps never exceeds five times the number of decimal digits of the smaller input. Consecutive Fibonacci numbers are the worst case. GCD(F(n+1), F(n)) takes exactly n steps, and since Fibonacci numbers grow as φⁿ (φ ≈ 1.618), n is proportional to the logarithm of the input.

That is a satisfying fact: the worst possible input for a 2300-year-old algorithm is the Fibonacci sequence, and the analysis proving it only appeared 44 years after the first sequence was named. Lamé's theorem was also the first published analysis of an algorithm's computational complexity. Your interview prep is built on two millennia of good ideas.

For why O(log n) appears wherever halving is involved, see O(log n) Time Complexity Is Not a Coincidence. For the recursive version's stack depth, see Recursion Time Complexity.

Version	Time	Space
Naive	O(min(a, b))	O(1)
Euclidean (recursive)	O(log min(a, b))	O(log min(a, b))
Euclidean (iterative)	O(log min(a, b))	O(1)

LCM Is GCD in Disguise

The least common multiple is the smallest positive integer divisible by both a and b. It links to GCD through:

LCM(a, b) = a × b / GCD(a, b)

Compute it this way in code:

def lcm(a: int, b: int) -> int:
    return a // gcd(a, b) * b

Divide first, then multiply. Writing a * b // gcd(a, b) risks overflow in languages with fixed-width integers (Java, C++, Go) because the product a × b may exceed the integer ceiling before the division brings it back down. a // gcd(a, b) is always ≤ a, so the subsequent multiplication is safe.

This is a classic trap. The formula is mathematically equivalent either way. The overflow behavior is not.

Interview Problems That Actually Use GCD

More places than most prep material covers.

Direct computation. Some problems just ask for GCD or LCM. These are usually warm-up questions. The expectation is that you implement Euclidean without hesitation and state the complexity correctly. If you loop from min(a, b) downward, you probably won't get another question.

Scheduling and synchronization. "Event A repeats every 6 days. Event B repeats every 4 days. How often do they coincide?" is LCM(6, 4) = 12. These word problems always reduce to the LCM formula, which needs GCD.

Coprimality checks. gcd(a, b) == 1 tests whether two numbers share no prime factors. This shows up in fraction reduction (is a/b already in lowest terms?), cryptography-adjacent problems, and combinatorics questions like "how many integers in [1, n] are coprime with n?"

GCD of Strings (LeetCode 1071). Two strings s and t have a "GCD string" if some shorter string, repeated, produces both. The GCD string has length gcd(len(s), len(t)), which you verify by checking if s + t == t + s. This is a genuinely sneaky pattern to recognize. Nothing about the problem statement says GCD. You have to see it.

Array GCD problems. GCD is associative and commutative, so the GCD of an array is computed incrementally. Python makes this a one-liner:

from math import gcd
from functools import reduce

def array_gcd(nums: list[int]) -> int:
    return reduce(gcd, nums)

A common pattern: "Can you reduce every element to 1 using GCD of adjacent pairs?" The GCD of the entire array must be 1 for this to be possible.

Fraction arithmetic in simulations. Any problem that accumulates fractions and asks for an exact answer needs reduction at each step to prevent numerator/denominator explosion. GCD is what makes that reduction work.

Practicing these patterns under realistic time pressure matters. If you want to sharpen number theory problems alongside your DSA prep, SpaceComplexity runs voice-based mock interviews with rubric-based feedback that covers exactly these problem types.

Key Takeaways

GCD(a, b) is the largest integer dividing both a and b with no remainder.
The Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), base case GCD(a, 0) = a.
Time complexity is O(log min(a, b)). Worst case is consecutive Fibonacci numbers.
The iterative version runs in O(1) space. Use it in interviews.
LCM(a, b) = a // gcd(a, b) * b. Divide first to avoid overflow.
GCD appears in scheduling, coprimality checks, fraction reduction, string pattern matching, and array problems.
Python 3.5+ has math.gcd(). C++17 has std::gcd. Java and JavaScript have no built-ins for plain integers.