GCD (Euclid's Algorithm)

Used in: Greatest Common Divisor of Strings (LC 1071)
Time: O(log(min(a, b)))

What is GCD?

The greatest common divisor is the biggest number that divides both numbers evenly.

• gcd(12, 18) = 6
• gcd(6, 4) = 2
• gcd(3, 8) = 1 (nothing in common except 1)

Core idea

Keep asking “what’s left over?” until nothing is.

“Left over” = the remainder. You have 6 sweets and make groups of 4: that’s 1 group, with 2 left over. In code, 6 % 4 = 2.

The rule:

1. Divide the big number by the small number and look at what’s left over.
2. If nothing is left over, the small number is your answer.
3. If something is left over, go again using the small number and the leftover.

Worked examples

gcd(6, 4)

1. 6 in groups of 4 → 2 left over → keep 4 and 2
2. 4 in groups of 2 → 0 left over → stop
3. Answer: 2

gcd(18, 12)

1. 18 in groups of 12 → 6 left over → keep 12 and 6
2. 12 in groups of 6 → 0 left over → stop
3. Answer: 6

Code (TypeScript)

function gcd(a: number, b: number): number {
  while (b !== 0) {          // something is still left over
    const leftover = a % b;  // what's left after splitting a into groups of b
    a = b;                   // the small number becomes the new big one
    b = leftover;            // the leftover becomes the new small one
  }
  return a;                  // nothing left over, so a is the answer
}
 
// Same thing in one line (recursive)
const gcdRec = (a: number, b: number): number => (b === 0 ? a : gcdRec(b, a % b));

Gotchas

• Order doesn’t matter. If a < b, the first step just swaps them: 4 % 6 = 4, so (4, 6) becomes (6, 4).
• gcd(n, 0) = n, which is why the loop stops when b is 0.
• The slow way (count down from the smaller number) works, but it tries far more numbers.

Why it works (simple version)

Any number that fits evenly into both 6 and 4 must also fit evenly into what’s left over (2). So the leftover keeps the same common divisors, just with smaller numbers. Keep shrinking until it’s obvious.