LCM & GCD in Python --- From First Principles to Optimized Solutions

Problem
Given two integers a and b, compute their LCM (least common multiple) and GCD (greatest common divisor).
Example: a = 5, b = 10 → LCM = 10, GCD = 5.

Practice Mock Question - https://www.smartmockinterview.com/plan/compute-lcm-and-gcd-of-given-integer-numbers-837

[1) What are GCD and LCM?
[2) Key Identity (Why it's powerful)
[3) Euclid's Algorithm (Fast GCD)
[4) Python Implementations
- A. From Scratch (Interview-Friendly)
- B. Production-Ready (stdlib)
[5) Extending to N Numbers
[6) Edge Cases & Pitfalls
[7) Binary GCD (Stein's Algorithm)
[8) Worked Examples
[9) Complexity Summary
[10) Unit Tests
[11) Benchmark Snippet
[12) Interview Notes & Gotchas
[13) TL;DR Copy/Paste
[14) Practice Prompts

What are GCD and LCM?

GCD(a, b): the largest integer that divides both a and b.
LCM(a, b): the smallest positive integer that both a and b divide.

They appear everywhere: simplifying fractions, number theory, scheduling problems, cryptography, and more.

Key Identity (Why it's powerful)

For non-zero integers:

lcm(a, b) * gcd(a, b) = |a * b|

This lets you compute the LCM efficiently if you already have the GCD:

lcm(a, b) = 0 if a == 0 or b == 0 lcm(a, b) = |a * b| / gcd(a, b) otherwise

Note: In integer code, compute a // gcd * b (in that order) to keep intermediates small.

Euclid's Algorithm (Fast GCD)

Euclid's algorithm uses repeated remainders:

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

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

Python Implementations

A. From Scratch (Interview-Friendly)

`def gcd_euclid(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a  # non-negative

def lcm_from_gcd(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    g = gcd_euclid(a, b)
    return abs(a // g * b)  # compute // first, then multiply`

A single function that returns both:

`def lcm_and_gcd(a: int, b: int):
    g = gcd_euclid(a, b)
    l = 0 if (a == 0 or b == 0) else abs(a // g * b)
    return l, g`

B. Production-Ready (stdlib)

Use Python's optimized C implementations when available:

import math

def lcm_and_gcd_fast(a: int, b: int):
    g = math.gcd(a, b)  # Python 3.5+
    try:
        l = math.lcm(a, b)  # Python 3.9+
    except AttributeError:
        l = 0 if a == 0 or b == 0 else abs(a // g * b)
    return l, g

Why prefer stdlib? It's faster, well-tested, and more readable.

Extending to N Numbers

For a list nums = [n1, n2, ..., nk], fold pairwise:

`from functools import reduce
import math

def gcd_list(nums):
    # gcd(0, x) = |x|, so 0 is a neutral element here
    return reduce(math.gcd, (abs(x) for x in nums), 0)

def _lcm_pair(a, b):
    if a == 0 or b == 0:
        return 0
    return abs(a // math.gcd(a, b) * b)

def lcm_list(nums):
    # lcm(1, x) = |x|, so 1 is convenient as a start
    return reduce(_lcm_pair, nums, 1)`

Complexity: O(k * log V) where k is the number of values and V their magnitude.

Edge Cases & Pitfalls

Zeros
- gcd(0, 0) = 0 (Python convention).
- lcm(a, 0) = 0 for any a.
Negatives
- Return non-negative GCD/LCM; use abs(...).
Large Integers
- Python integers are arbitrary precision, but still avoid abs(a*b) first---prefer a // gcd * b.
Order of Operations
- Always divide before multiply to reduce intermediate sizes.

Binary GCD (Stein's Algorithm)

Avoids division/mod, using only shifts and subtraction. Mostly educational in Python (since math.gcd is excellent), but good to know:

`def gcd_binary(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    if a == 0 or b == 0:
        return a | b
    shift = 0
    while ((a | b) & 1) == 0:
        a >>= 1; b >>= 1; shift += 1
    while (a & 1) == 0:
        a >>= 1
    while b:
        while (b & 1) == 0:
            b >>= 1
        if a > b:
            a, b = b, a
        b -= a
    return a << shift`

Worked Examples

`print(lcm_and_gcd_fast(5, 10))     # (10, 5)
print(lcm_and_gcd_fast(21, 6))     # (42, 3)
print(lcm_and_gcd_fast(-12, 18))   # (36, 6)
print(lcm_list([4, 6, 8]))         # 24
print(gcd_list([24, 60, 36]))      # 12
print(lcm_and_gcd_fast(0, 7))      # (0, 7)
print(lcm_and_gcd_fast(0, 0))      # (0, 0)`

Dry run for gcd_euclid(21, 6):

(a, b) = (21, 6)
(a, b) = (6, 21 % 6 = 3)
(a, b) = (3, 6 % 3 = 0) → return 3.

Complexity Summary

Euclid GCD: O(log min(a, b)) time, O(1) space.
LCM via GCD: same order.
List versions: O(k * log V).

Unit Tests

`def _test():
    cases = [
        (5, 10, (10, 5)),
        (21, 6, (42, 3)),
        (-12, 18, (36, 6)),
        (0, 7, (0, 7)),
        (0, 0, (0, 0)),
        (1, 1, (1, 1)),
        (13, 17, (221, 1)),
    ]
    for a, b, expected in cases:
        assert lcm_and_gcd_fast(a, b) == expected
    assert gcd_list([24, 60, 36]) == 12
    assert lcm_list([4, 6, 8]) == 24
    print("All tests passed.")

if __name__ == "__main__":
    _test()`

Benchmark Snippet

Quick-and-dirty comparison of pure Python vs stdlib:

`import math, random, time

def gcd_py(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

def bench(fn, iters=20000):
    s = time.time()
    for _ in range(iters):
        a = random.randint(1, 10**12)
        b = random.randint(1, 10**12)
        fn(a, b)
    return time.time() - s

print("math.gcd:", bench(math.gcd))
print("python gcd:", bench(gcd_py))`

You should see math.gcd significantly faster.

Interview Notes & Gotchas

Lead with Euclid's algorithm; derive LCM from the identity.
State conventions for zeros and negatives.
Mention order of operations (a // gcd * b) to avoid big temporaries.
For "optimize further," say: use math.gcd/math.lcm; for N numbers, reduce pairwise.
If mod/div is "expensive," mention binary GCD.

TL;DR Copy/Paste

`import math
from functools import reduce

def gcd(a: int, b: int) -> int:
    return math.gcd(a, b)

def lcm(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    return abs(a // math.gcd(a, b) * b)

def lcm_and_gcd(a: int, b: int):
    g = math.gcd(a, b)
    try:
        return math.lcm(a, b), g
    except AttributeError:
        return (0 if a == 0 or b == 0 else abs(a // g * b)), g

def gcd_list(nums):
    return reduce(math.gcd, (abs(x) for x in nums), 0)

def _lcm_pair(a, b):
    if a == 0 or b == 0:
        return 0
    return abs(a // math.gcd(a, b) * b)

def lcm_list(nums):
    return reduce(_lcm_pair, nums, 1)`

Practice Prompts

Given n tasks that repeat every t_i minutes, when do they align?
→ Compute lcm_list(t_i).
Reduce a fraction p/q to lowest terms.
→ Divide numerator & denominator by gcd(p, q).
Implement gcd recursively and compare its performance to iterative Euclid.
Extend lcm_list to ignore zeros and explain why that changes semantics.

Happy coding! You now have the theory, clean Python solutions, optimizations, and tests to nail any GCD & LCM question. Mock Interview www.smartmockinterview.com

Practice Mock Question - https://www.smartmockinterview.com/plan/compute-lcm-and-gcd-of-given-integer-numbers-837

Table of Contents

A. From Scratch (Interview-Friendly)

B. Production-Ready (stdlib)