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
aandbis the largest number that divides both. - The LCM (least common multiple) is the smallest positive number that both
aandbdivide. - 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:
gcd(0, 5)isNone.range(0, 0, -1)is empty, the loop never runs, and a function that ends withoutreturnreturnsNone.- 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)(fromfunctools) keeps a dictionary from arguments to results, so eachfib(k)is computed once: 36 calls forfib(35). O(n) time, O(n) space. (LRU means "least recently used": with amaxsize, 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
- 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.
- How do you get the LCM from the GCD?
a * b // gcd(a, b)(ora // gcd(a, b) * bto keep intermediate numbers smaller in other languages). - Why can't you use
/for the LCM in Python? It returns a float, which loses digits above about 2⁵³. - 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. - 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.setrecursionlimitis risky. - What is memoization? Caching the results of a function by its arguments, so repeated calls are free;
functools.lru_cache/functools.cachedo it with one decorator. - Time complexity of naive recursive Fibonacci? Exponential, O(2ⁿ) (more exactly O(φⁿ), φ ≈ 1.618).
- Fibonacci in O(1) space? Keep only the last two values:
a, b = b, a + b. - Is there something faster than O(n) for Fibonacci? Yes, matrix exponentiation or "fast doubling" in O(log n) arithmetic operations.
- 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 % bis O(log n); counting down is O(n) and returnsNonefor 0. - LCM:
a * b // gcd(a, b); never/, which gives a rounded float.math.gcd/math.lcmare built in. - Factorials: Python ints never overflow, but recursion stops at ~1000 calls (
RecursionError) andstr()stops at 4300 digits (sys.set_int_max_str_digits). - Fibonacci: naive recursion is exponential (30 million calls for fib(35));
@lru_cachemakes 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.