Compute n!, read "n factorial". It is 1 \times 2 \times 3 \times \dots \times n. So 5! = 120.
Count how many zeros n! ends with, without computing n!. 10! = 3{,}628{,}800 ends with two zeros.
Compute 100! in a language whose integers hold only about 19 digits.
The factorial counts arrangements. Three books on a shelf can be ordered in 3! = 6 ways. Pick the first book from 3, the second from the 2 left, the last is forced. 3 \times 2 \times 1. By definition 0! = 1, because there is exactly one way to arrange nothing.
def factorial(n: int) -> int: if n < 0: raise ValueError("factorial is not defined for negative numbers") result = 1 # (1) for i in range(2, n + 1): # (2) result *= i return resultprint(factorial(5)) # → 120print(factorial(0)) # → 1print(factorial(20)) # → 2432902008176640000
(1) Start at 1, not 0. Anything multiplied by 0 stays 0. Starting at 1 also makes 0! and 1! come out as 1 with no special case, because the loop does not run.
(2) Multiply in 2, 3, and so on up to n. Multiplying by 1 changes nothing, so we skip it.
n! = n \times (n-1)!. The problem contains a smaller copy of itself, which is Move 5 from 4.0.0.
python
def factorial_rec(n: int) -> int: if n <= 1: return 1 # base case return n * factorial_rec(n - 1) # smaller copyprint(factorial_rec(6)) # → 720
Which is better? The loop. The recursive version keeps one unfinished call on the stack for each number, so it uses O(n) memory. Python stops recursion at about 1,000 calls by default. So factorial_rec(5000) crashes with RecursionError, while the loop handles it easily. Interviewers often ask which one is better, and this is the reason.
Factorials grow faster than any power. 10! is about 3.6 million. 20! is about 2.4 \times 10^{18}, which is close to the limit of a 64-bit integer. 21! does not fit in one. 100! has 158 digits. Python's integers grow as needed, so Python prints all of them. In Java or C, long overflows at 21!.
A number ends in zero when it is divisible by 10. Every 10 is 2 \times 5. So each trailing zero needs one 2 and one 5 among the factors of n!.
Among 1, 2, \dots, n, every second number gives a factor 2. Only every fifth number gives a 5. So 2s are always plentiful, and 5s are what run out first. The number of trailing zeros is just the number of 5s in the prime factorisation of n!.
Every multiple of 5 gives at least one 5. There are 100 // 5 = 20 of them.
But 25, 50, 75 and 100 are multiples of 25 = 5 \times 5. They each give a second 5. There are 100 // 25 = 4 of them.
Multiples of 125 would give a third 5. There are 100 // 125 = 0 of them.
Total: 20 + 4 + 0 = 24 trailing zeros.
Each multiple of 25 is counted once in the first line and once more in the second. That is exactly right, because it holds two 5s. A multiple of 125 would be counted three times, matching its three 5s.
python
def trailing_zeros(n: int) -> int: count = 0 power = 5 while power <= n: # (1) count += n // power # (2) power *= 5 return countprint(trailing_zeros(10)) # → 2print(trailing_zeros(100)) # → 24print(trailing_zeros(1000)) # → 249
(1) Go through 5, 25, 125, and so on, while they are not bigger than n.
(2)n // power counts the numbers up to n that hold this power of 5.
A neater version divides n instead of growing the power. It gives the same sum.
python
def trailing_zeros_v2(n: int) -> int: count = 0 while n >= 5: n //= 5 count += n return countprint(trailing_zeros_v2(100)) # → 24
For 100: first 100 // 5 = 20, then 20 // 5 = 4, then 4 // 5 = 0 stops it. 20 + 4 = 24.
The loop runs once per power of 5, which is O(\log_5 n) steps. Computing 1000! to count its zeros would mean building a 2,568-digit number. This answers in 4 steps.
The general rule is Legendre's formula, from the French mathematician Adrien-Marie Legendre in 1808. The power of any prime p in n! is \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \lfloor n/p^3 \rfloor + \dots The brackets \lfloor \ \rfloor mean "round down", which is what // does.
Python has big integers built in, so factorial(100) simply works. Interviewers sometimes ask "how would you do it in C?" The answer is to do what you did at school with long multiplication. Store the number as a list of digits, and multiply the list by each new number, carrying as you go.
python
def big_factorial(n: int) -> str: digits = [1] # (1) the number 1, digits stored right to left for x in range(2, n + 1): carry = 0 for i in range(len(digits)): prod = digits[i] * x + carry # (2) digits[i] = prod % 10 # (3) carry = prod // 10 while carry: # (4) digits.append(carry % 10) carry //= 10 return "".join(map(str, reversed(digits))) # (5)print(big_factorial(25)) # → 15511210043330985984000000print(len(big_factorial(100))) # → 158
(1) Keep the ones digit first. Then a number that grows only needs new digits at the end of the list, which is cheap.
(2) Multiply one digit by x and add the carry from the digit before. This is one column of long multiplication.
(3) Keep the last digit in this place. Carry the rest to the next place.
(4) After the last digit, the carry may still hold several digits. Add them as new places.
(5) Reverse to print the most significant digit first.
Multiplying 120 (stored as [0, 2, 1]) by 6:
place
digit × 6 + carry
keep
carry
ones
0 \times 6 + 0 = 0
0
0
tens
2 \times 6 + 0 = 12
2
1
hundreds
1 \times 6 + 1 = 7
7
0
The result is [0, 2, 7], which reads as 720. That is 6!.
The loop: n multiplications. With fixed-size numbers that is O(n). With growing numbers each multiplication gets slower as the number gets longer, so the real cost is higher. Trailing zeros: O(\log n). The digit-list method: O(n \times d), where d is the number of digits in n!, about 158 for n = 100.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"Loop or recursion: which is better for factorial?" The loop. Recursion keeps one unfinished call in memory for each number. Python also stops recursion at about 1,000 calls, so factorial_rec(5000) crashes. The loop has neither problem.
"How many zeros does 100! end with?" 24. Count the factors of 5: 100 // 5 = 20, and 100 // 25 = 4, so 20 + 4 = 24. The numbers 25, 50, 75 and 100 each hold two 5s, which is why the second step is needed. Saying 20 is the usual mistake.
"Why count 5s and not 2s?" Each trailing zero needs one 2 and one 5. There are always more 2s than 5s. So the 5s run out first, and they decide the count.
"What is 0!?" It is 1. There is exactly one way to arrange zero things. It also keeps the rule 1! = 1 \times 0! true.
"How would you store 100! in C?" Keep the number as a list of digits. Multiply it digit by digit with a carry, like long multiplication on paper.
One thing to volunteer: "Adding two big numbers stored as strings works the same way, digit by digit with a carry."
Next:4.0.8 Fibonacci, Three Ways. The textbook example of a simple recursion that wastes almost all its time.