SyntaxPilot
Courses/Python Coding Questions/Lesson 3
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 3 of 30

Number questions III

GCD and LCM (Euclid, math.gcd)factorial and big integers (Python has no overflow)n-th Fibonacci (loop vs naive recursion vs functools.lru_cache)

These are the notes for Python Coding Questions, episode 3. Three classics: the greatest common divisor (and least common multiple), factorials of huge numbers, and the n-th Fibonacci number. Each has an obvious answer that works for small inputs and breaks for big ones in a different way: too slow, a float instead of an exact integer, and Python's own limits on recursion depth and on printing huge integers.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real; timings depend on the machine, so compare them, don't copy them.

Q1: GCD and LCM

Definitions.

  • The GCD (greatest common divisor, also called HCF, highest common factor) of a and b is the largest number that divides both.
  • The LCM (least common multiple) is the smallest positive number that both a and b divide.
  • Two numbers with GCD 1 are coprime.
  • gcd(0, n) = n, because every number divides 0.
Input GCD LCM
12, 18 6 36
4, 6 2 12
7, 5 1 (coprime) 35
100, 75 25 300
0, 5 5 0

Real-life example: 12 laddoos and 18 barfis packed into identical gift boxes with nothing left over: the most boxes you can make is gcd(12, 18) = 6 (each box: 2 laddoos, 3 barfis).

The obvious attempt: count down from min(a, b)

import time

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

print(gcd(12, 18), gcd(7, 5), gcd(100, 75), gcd(0, 5))
start = time.perf_counter()
print(gcd(50_000_017, 50_000_021))
print(f"{time.perf_counter() - start:.2f} seconds")

Output:

6 1 25 None
1
1.30 seconds

Two problems:

  1. gcd(0, 5) is None. range(0, 0, -1) is empty, the loop never runs, and a function that ends without return returns None.
  2. It is slow. For two coprime numbers the loop counts all the way down from 50,000,017 to 1: O(min(a, b)) steps. With 12-digit numbers it would take hours.

Euclid's algorithm

Real-life example: tile an 18 × 12 floor with the biggest square tiles that fit exactly. Lay 12 × 12 squares: a 6 × 12 strip is left (18 % 12 = 6). Any tile that fits the whole floor must also fit that strip, so tile the 12 × 6 strip next: 6 × 6 tiles fit exactly (12 % 6 = 0). The answer is 6.

The rule: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.

import time

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

print(gcd(12, 18), gcd(7, 5), gcd(100, 75), gcd(0, 5))
start = time.perf_counter()
print(gcd(50_000_017, 50_000_021))
print(f"{time.perf_counter() - start:.6f} seconds")

Output:

6 1 25 5
1
0.000008 seconds

a, b = b, a % b is tuple assignment: both right-hand values are computed first, then assigned, so no temporary variable is needed.

step a b a % b
1 48 18 12
2 18 12 6
3 12 6 0
4 6 0 stop → 6

Complexity: the remainder at least halves every two steps, so Euclid takes O(log min(a, b)) steps, a few hundred even for numbers with hundreds of digits. Space O(1).

LCM: the float trap

a × b = gcd(a, b) × lcm(a, b), so lcm = a * b / gcd:

import math

def lcm(a, b):
    return a * b / math.gcd(a, b)

print(lcm(4, 6))
print(lcm(123_456_789_123, 987_654_321_987))

Output:

12.0
4.064421045198953e+22

/ always returns a float (episode 1), and a float keeps only about 16 significant digits: the 23-digit answer is rounded. Since a * b is always divisible by the GCD, floor division // is exact:

import math

def lcm(a, b):
    return a * b // math.gcd(a, b)

print(lcm(4, 6))
print(lcm(123_456_789_123, 987_654_321_987))
print(math.lcm(123_456_789_123, 987_654_321_987))

Output:

12
40644210451989533782467
40644210451989533782467

math.gcd and math.lcm accept any number of arguments (Python 3.9+): math.gcd(84, 126, 210) is 42 and math.lcm(4, 6, 10) is 60.

Q2: Factorial

Definition. n! = 1 × 2 × 3 × ... × n, and 0! = 1. It counts the ways to arrange n things: 5 friends can stand in a line in 5! = 120 orders. It is also defined recursively: n! = n × (n - 1)!.

The obvious attempt: recursion

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5), factorial(20))
print(factorial(25))
print(factorial(5000))

Output:

120 2432902008176640000
15511210043330985984000000
Traceback (most recent call last):
  File "main.py", line 8, in <module>
    print(factorial(5000))
          ~~~~~~~~~^^^^^^
  File "main.py", line 4, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  File "main.py", line 4, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  File "main.py", line 4, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
  • 25! is exact: 26 digits. In C or Java a 64-bit integer overflows after 20!; Python integers grow as large as memory allows (arbitrary precision).
  • 5000! fails with RecursionError: maximum recursion depth exceeded. Each call waits for the next one on the call stack; Python stops at about 1000 nested calls (sys.getrecursionlimit() is 1000) to protect the program from running out of memory.

The fix: a loop

import math

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

big = factorial(5000)
print(big == math.factorial(5000))
print(len(str(big)), "digits")

Output:

True
Traceback (most recent call last):
  File "main.py", line 11, in <module>
    print(len(str(big)), "digits")
              ~~~^^^^^
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

The loop matches math.factorial, but str() refuses: since Python 3.11, converting an integer with more than 4300 digits to text (or text to an integer) raises ValueError, because the conversion is slow (quadratic) and huge inputs could freeze a server. The error message names the fix:

import math, sys

sys.set_int_max_str_digits(0)        # 0 = no limit on digits
big = math.factorial(5000)
s = str(big)
print(len(s), "digits")
print(s[:20] + "...")
print("trailing zeros:", len(s) - len(s.rstrip("0")))

Output:

16326 digits
42285779266055435222...
trailing zeros: 1249

sys.set_int_max_str_digits(0) removes the limit for this program. Complexity: n − 1 multiplications, O(n) of them, but each one is on a number that keeps getting longer, so the real time grows faster than n. In an interview, say "O(n) multiplications of growing numbers".

Q3: The n-th Fibonacci number

Definition. fib(0) = 0, fib(1) = 1, fib(n) = fib(n - 1) + fib(n - 2): 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... Each number is the sum of the two before it (sunflower seed spirals and pine cones follow this sequence).

The obvious attempt: recursion straight from the definition

A global counter (episode 14) counts the calls:

import time

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(n) for n in range(10)])
calls = 0
start = time.perf_counter()
print(fib(35), "after", calls, "calls")
print(f"{time.perf_counter() - start:.2f} seconds")

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
9227465 after 29860703 calls
1.20 seconds

Why so many calls: fib(35) calls fib(34) and fib(33); fib(34) calls fib(33) again, and so on. The same small answers are recomputed millions of times. The number of calls grows like 1.618ⁿ (the golden ratio): exponential time, usually written O(2ⁿ).

Memoization with @lru_cache

Real-life example: if the teacher asks "17 × 23?" five times, you write 391 in your notebook the first time and read it after that. Remembering answers you've already computed is memoization.

import time
from functools import lru_cache

@lru_cache(maxsize=None)            # remember every answer
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

start = time.perf_counter()
print(fib(35))
print(f"{time.perf_counter() - start:.4f} seconds")
print(fib(2000))

Output:

9227465
0.0001 seconds
Traceback (most recent call last):
  File "main.py", line 13, in <module>
    print(fib(2000))
          ~~~^^^^^^
  File "main.py", line 8, in fib
    return fib(n - 1) + fib(n - 2)
           ~~~^^^^^^^
  File "main.py", line 8, in fib
    return fib(n - 1) + fib(n - 2)
           ~~~^^^^^^^
  File "main.py", line 8, in fib
    return fib(n - 1) + fib(n - 2)
           ~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
  • @lru_cache(maxsize=None) (from functools) keeps a dictionary from arguments to results, so each fib(k) is computed once: 36 calls for fib(35). O(n) time, O(n) space. (LRU means "least recently used": with a maxsize, the oldest entries are dropped.)
  • But fib(2000) still raises RecursionError: the first call goes 2000 calls deep before anything is cached. Memoization fixes the time, not the depth.

The fix: two variables and a loop

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print([fib(n) for n in range(10)])
print(fib(35))
print(len(str(fib(2000))), "digits")
print(str(fib(2000))[:30] + "...")

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
9227465
418 digits
422469633339230487870672560234...
Method Time Extra space Limit
naive recursion O(2ⁿ) O(n) call stack slow from n ≈ 35
@lru_cache O(n) O(n) cache + stack RecursionError near n ≈ 1000
two-variable loop O(n) O(1) none (only the size of the numbers)

Common mistakes (and what you really see)

Mistake What you see Why Fix
count down from min(a, b) gcd(0, 5) → None; seconds for big coprime numbers empty range; O(min(a, b)) Euclid: a, b = b, a % b
a * b / gcd(a, b) 12.0, 4.064421045198953e+22 / always gives a float a * b // gcd(a, b), math.lcm
recursive factorial(5000) RecursionError: maximum recursion depth exceeded about 1000 nested calls max a loop, or math.factorial
str() of a 16,326-digit int ValueError: Exceeds the limit (4300 digits) for integer string conversion a safety limit since Python 3.11 sys.set_int_max_str_digits(0)
naive recursive fib(n) ~30 million calls for fib(35) the same answers again and again @lru_cache, or the loop
@lru_cache fib(2000) RecursionError the first call is still 2000 deep the two-variable loop
sys.setrecursionlimit(10**6) "to fix it" the program can crash with no Python error at all the real C stack overflows write the loop instead

Your turn: trailing zeros of n! (solution)

Question. How many zeros are at the end of n!? 5! = 120 → 1, 10! → 2, 5000! → 1249. Do it without computing n!.

Solution

Each trailing zero is a factor 10 = 2 × 5. There are always more 2s than 5s among 1..n, so count the 5s: every multiple of 5 gives one, every multiple of 25 one more, every multiple of 125 one more, and so on.

def trailing_zeros(n):
    count = 0
    power = 5
    while power <= n:
        count += n // power
        power *= 5
    return count

for n in [5, 10, 25, 100, 5000, 10**18]:
    print(n, trailing_zeros(n))

Output:

5 1
10 2
25 6
100 24
5000 1249
1000000000000000000 249999999999999995

1249 matches the count we got from the 16,326-digit string. Time O(log₅ n), space O(1): it works for 10¹⁸, whose factorial could never be computed.

Practice questions (with solutions)

1. GCD and LCM of a whole list.

Solution
import math
from functools import reduce

nums = [84, 126, 210]
print(reduce(math.gcd, nums), math.gcd(*nums), math.lcm(4, 6, 10))

Output:

42 42 60

reduce(f, [a, b, c]) computes f(f(a, b), c). Since Python 3.9 math.gcd and math.lcm take many arguments directly.

2. Sum of the digits of 100!.

Solution
import math
print(sum(int(ch) for ch in str(math.factorial(100))))

Output:

648

100! has 158 digits, under the 4300-digit limit, so str() works without changing it.

3. The index of the first Fibonacci number with 1000 digits.

Solution
a, b, i = 0, 1, 0
while len(str(a)) < 1000:
    a, b = b, a + b
    i += 1
print(i)

Output:

4782

a is fib(i) at every step. Python's big integers make this a 4-line answer.

4. Simplify a fraction. 84/126 → 2/3.

Solution
import math

def simplify(num, den):
    g = math.gcd(num, den)
    return num // g, den // g

print(simplify(84, 126), simplify(10, 4), simplify(0, 7))

Output:

(2, 3) (5, 2) (0, 1)

Quick quiz

What does this print?

a, b = 48, 18
while b:
    a, b = b, a % b
    print(a, b)

(A) 18 12 / 12 6 / 6 0 (B) 48 18 / 18 12 / 12 6 (C) 18 12 / 12 6 (D) 6

Answer

(A). 48 % 18 = 12 → (18, 12); 18 % 12 = 6 → (12, 6); 12 % 6 = 0 → (6, 0). while b: means "while b is not 0", so the loop stops, and the GCD is 6.

18 12
12 6
6 0

Interview questions

  1. Explain Euclid's algorithm and its complexity. gcd(a, b) = gcd(b, a % b) until b = 0; O(log min(a, b)) because the remainder at least halves every two steps.
  2. How do you get the LCM from the GCD? a * b // gcd(a, b) (or a // gcd(a, b) * b to keep intermediate numbers smaller in other languages).
  3. Why can't you use / for the LCM in Python? It returns a float, which loses digits above about 2⁵³.
  4. Can a factorial overflow in Python? No, ints are arbitrary precision; but the recursion depth (~1000) and the 4300-digit str() limit are real limits.
  5. What is a RecursionError and how do you avoid it? Too many nested calls; rewrite the recursion as a loop (or use an explicit stack). Raising the limit with sys.setrecursionlimit is risky.
  6. What is memoization? Caching the results of a function by its arguments, so repeated calls are free; functools.lru_cache / functools.cache do it with one decorator.
  7. Time complexity of naive recursive Fibonacci? Exponential, O(2ⁿ) (more exactly O(φⁿ), φ ≈ 1.618).
  8. Fibonacci in O(1) space? Keep only the last two values: a, b = b, a + b.
  9. Is there something faster than O(n) for Fibonacci? Yes, matrix exponentiation or "fast doubling" in O(log n) arithmetic operations.
  10. How many trailing zeros does n! have? Σ n // 5ᵏ, counting the factors of 5.

Glossary

Term Meaning Example
GCD / HCF Greatest common divisor: largest number dividing both gcd(12, 18) = 6
LCM Least common multiple: smallest number both divide lcm(4, 6) = 12
Coprime Two numbers whose GCD is 1 7 and 5
Euclid's algorithm gcd(a, b) = gcd(b, a % b), until b = 0 gcd(48, 18) → 6 in 3 steps
Tuple assignment Assign several variables at once from computed values a, b = b, a % b
math.gcd, math.lcm Built-in GCD and LCM, any number of arguments math.lcm(4, 6, 10) → 60
Factorial n! 1 × 2 × ... × n; 0! = 1 5! = 120
Arbitrary precision Integers of any size, limited only by memory 25! exact, 26 digits
Recursion A function that calls itself factorial(n - 1)
Call stack The chain of calls waiting for each other to finish 5000 nested factorial calls
RecursionError Raised when calls nest deeper than the limit (~1000) factorial(5000)
sys.getrecursionlimit() The current recursion limit 1000
sys.set_int_max_str_digits(n) Changes the int ↔ str digit limit; 0 means no limit needed for str(math.factorial(5000))
Trailing zeros Zeros at the end of a number 5000! has 1249
Fibonacci number Each is the sum of the two before it 0, 1, 1, 2, 3, 5, 8
Exponential time Steps roughly double when n grows by 1 naive fib
Memoization Remembering results of earlier calls @lru_cache
functools.lru_cache Decorator that caches a function's results @lru_cache(maxsize=None)
global Lets a function assign to a module-level variable global calls
functools.reduce Folds a list with a two-argument function reduce(math.gcd, nums)
O(log n) Steps grow with the number of digits Euclid
O(2ⁿ) Steps roughly double with each +1 to n naive Fibonacci

Summary

  • GCD: Euclid's a, b = b, a % b is O(log n); counting down is O(n) and returns None for 0.
  • LCM: a * b // gcd(a, b); never /, which gives a rounded float. math.gcd / math.lcm are built in.
  • Factorials: Python ints never overflow, but recursion stops at ~1000 calls (RecursionError) and str() stops at 4300 digits (sys.set_int_max_str_digits).
  • Fibonacci: naive recursion is exponential (30 million calls for fib(35)); @lru_cache makes it O(n) but still hits the depth limit; the two-variable loop is O(n) time and O(1) space.
  • Trailing zeros of n!: count the factors of 5, no big numbers needed.

Next episode: Number questions IV: decimal ↔ binary, counting set bits, and a one-line power-of-two check.