GCD

Pattern: Euclidean algorithm

Idea: Common divisors of (a, b) = Common divisors of (b, r)

---

💻 Code

def gcd(a, b):
    if b == 0:
        return a

    return gcd(b, a % b)

Time complexity - O(log(min(a, b)). See this Aux. Space complexity - O(1)

[!NOTE] Note No need to ensure a ≥ b—if a < b, the first modulo operation (a % b = a) automatically swaps the numbers.

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder.

Example:

GCD(12, 18) = 6

Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 18: 1, 2, 3, 6, 9, 18

Greatest common factor = 6

---

Naive Approach

Idea

Check every number from 1 to min(a, b) and keep updating the largest common divisor.

Python

def gcd(a, b):
    ans = 1

    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            ans = i

    return ans

Better Naive

Start from min(a, b) and return the first divisor found.

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

Complexity

• Time: O(min(a, b))

• Space: O(1)

Too slow for large numbers.

---

Euclidean Algorithm (Optimal)

Key Observation

The GCD does not change if the larger number is replaced by its remainder when divided by the smaller number.

GCD(a, b) = GCD(b, a % b)

This works because any number that divides both a and b also divides a % b, and vice versa.

---

Algorithm

Repeat until the remainder becomes 0.

while b != 0

    remainder = a % b

    a = b

    b = remainder

Answer = a

---

Dry Run

Find GCD(48, 18)

48 % 18 = 12

GCD(48,18)
↓

GCD(18,12)

18 % 12 = 6

GCD(18,12)
↓

GCD(12,6)

12 % 6 = 0

GCD(12,6)
↓

GCD(6,0)

Stop because b = 0.

Answer = 6

---

Python

def gcd(a, b):
    while b != 0:
        a, b = b, a % b

    return a

Recursive version:

def gcd(a, b):
    if b == 0:
        return a

    return gcd(b, a % b)

---

Why does it work?

Suppose

a = b × q + r

where

r = a % b

Any divisor of both a and b must also divide

a - (b × q) = r

So,

Common divisors of (a, b)
=
Common divisors of (b, r)

Hence,

GCD(a,b) = GCD(b,a%b)

---

Complexity

Each iteration significantly reduces the size of the numbers.

• Time: O(log(min(a, b)))

• Space: O(1) (iterative)

• Space: O(log(min(a, b))) (recursive call stack)

---

Interview Takeaways

• Naive: Check all divisors → O(min(a, b)).

• Optimal: Euclidean Algorithm → repeatedly replace (a, b) with (b, a % b).

• Stop when the second number becomes 0.

• The first number at that point is the GCD.

• Python’s built-in implementation is:

  import math
  math.gcd(a, b)