Problem Statement
Factorial Trailing Zeroes
You are given a number n. The factorial of n, written n!, means you multiply every whole number from 1 up to n together. So 5! = 5 * 4 * 3 * 2 * 1 = 120. A trailing zero is a zero at the very end of a number, like the single zero at the end of 120. Your job is to count how many trailing zeros n! has, without ever building the giant factorial number itself. Here is the key idea: a trailing zero only appears when you multiply by 10, and 10 = 2 * 5. So every trailing zero comes from one pair of a 2 and a 5 hiding among the factors. In a factorial there are always plenty of 2s (every even number gives you one), so the thing that runs out first is the 5s. That means the number of trailing zeros is exactly the number of times 5 shows up as a factor in the numbers from 1 to n. We count multiples of 5, then 25, then 125, then 625, and so on, because a number like 25 is 5 * 5 and hands you two 5s, 125 is 5 * 5 * 5 and hands you three, and so on.
Signals to notice
Brute force first
Compute n! and count — impossible for large n.
The key insight
Count factors of 5: n/5 + n/25 + n/125 + ... O(log n).
Trace it on n=30
start: count=0, n=30 iter1: n>=5 → n=30//5=6, count=0+6=6 (multiples of 5) iter2: n>=5 → n=6//5=1, count=6+1=7 (multiples of 25) iter3: n=1 < 5 → loop stops return count=7
What must stay true
Each trailing zero = one factor of 10 = 2×5. Factors of 2 are abundant, so count 5s. Multiples of 25 give extra 5s.
Shape of the loop
count = 0
while n >= 5:
n = n // 5 # collapse to next power of 5
count += n # add multiples of 5, then 25, then 125...
return countPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Only counting n/5 — multiples of 25, 125, etc. contribute additional factors of 5.