GCD and LCM Euclidean Algorithm in DSA Python

Mental Model

GCD is the biggest number that divides two numbers without leftovers. LCM is the smallest number both can fit into evenly. Euclid's method finds GCD by repeatedly subtracting or dividing until one number becomes zero.

Analogy: Imagine two ropes of different lengths. To find the longest piece you can cut both ropes into equal pieces without leftovers, you keep cutting the longer rope by the length of the shorter until one rope is fully cut. That length is the GCD. Then, the LCM is like finding the smallest length where both ropes can be joined end to end evenly.

a = 48
b = 18

GCD process:
48 -> 18 -> 12 -> 6 -> 0

LCM = (a * b) / GCD

48 -> 18
↑    ↑

Dry Run Walkthrough

Input: Find GCD and LCM of 48 and 18

Goal: Calculate the greatest common divisor and least common multiple of 48 and 18 using Euclid's algorithm

Step 1: Calculate remainder of 48 divided by 18 (48 % 18 = 12)

a = 18, b = 12

Why: Replace a with b and b with remainder to reduce problem size

Step 2: Calculate remainder of 18 divided by 12 (18 % 12 = 6)

a = 12, b = 6

Why: Continue reducing numbers to find GCD

Step 3: Calculate remainder of 12 divided by 6 (12 % 6 = 0)

a = 6, b = 0

Why: When remainder is zero, current a is GCD

Result:

GCD = 6
LCM = (48 * 18) / 6 = 144

Annotated Code

DSA Python

def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b  # reduce problem by remainder
    return a  # when b is zero, a is gcd

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

# Driver code
num1 = 48
num2 = 18
print(f"GCD of {num1} and {num2} is {gcd(num1, num2)}")
print(f"LCM of {num1} and {num2} is {lcm(num1, num2)}")

while b != 0:

loop until remainder is zero to find gcd

a, b = b, a % b # reduce problem by remainder

update a and b to smaller problem using remainder

return a # when b is zero, a is gcd

return gcd when remainder is zero

return (a * b) // gcd(a, b) # lcm from gcd

calculate lcm using gcd

Output

GCD of 48 and 18 is 6

LCM of 48 and 18 is 144

Complexity Analysis

Time: O(log(min(a, b))) because each step reduces the problem size by remainder which shrinks quickly

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Euclid's algorithm is much faster than checking all divisors up to min(a,b), which is O(min(a,b))

Edge Cases

One number is zero (e.g., gcd(0, 5))

GCD is the non-zero number, LCM is zero

DSA Python

while b != 0:

Both numbers are equal (e.g., gcd(7, 7))

GCD is the number itself, LCM is the same number

DSA Python

while b != 0:

One number divides the other exactly (e.g., gcd(12, 4))

GCD is the smaller number, LCM is the larger number

DSA Python

while b != 0:

When to Use This Pattern

When you need to find the greatest common divisor or least common multiple efficiently, look for Euclid's algorithm pattern because it quickly reduces the problem using remainders.

Common Mistakes

Mistake: Using subtraction repeatedly instead of modulo, which is slower
Fix: Use modulo operator (%) to reduce numbers faster

Mistake: Not handling zero inputs correctly, causing infinite loops
Fix: Check for zero and return the other number as gcd immediately

Summary

Finds the greatest common divisor and least common multiple of two numbers using Euclid's fast remainder method.

Use when you need efficient calculation of GCD or LCM for two integers.

The key insight is that GCD of two numbers equals the GCD of the smaller number and the remainder of the larger divided by the smaller.