Trailing Zeros of 100!: Puzzle and Step-by-Step Solution
Mental Math
Easy
Reported at SIG, Optiver, Akuna, Belvedere
The puzzle
How many zeros are at the end of 100! (100 factorial)?
Short answer: 24.
Step 1: Zeros come from tens, tens come from fives
Every trailing zero is a factor of 10 = 2 × 5. So the number of trailing zeros of 100! is the number of times 10 divides it, which is the smaller of the number of factors of 2 and the number of factors of 5 in 100!.
Factors of 2 are everywhere: every even number contributes at least one. Factors of 5 are much rarer. So the fives are the bottleneck, and the answer is simply the number of factors of 5 in 1 × 2 × ... × 100.
Step 2: Count the fives
The multiples of 5 up to 100 are 5, 10, 15, ..., 100. There are 100 / 5 = 20 of them, and each contributes at least one factor of 5.
Multiples of 25 contribute a second factor of 5: 25, 50, 75 and 100, which is 100 / 25 = 4 more. Multiples of 125 would contribute a third, but there are none below 100. So the total is 20 + 4 = 24.
Step 3: The general formula
For n!, the number of trailing zeros is floor(n/5) + floor(n/25) + floor(n/125) + ..., stopping when the power of 5 exceeds n. This is Legendre's formula for the exponent of a prime in a factorial, applied to 5.
Worked examples: 1000! has 200 + 40 + 8 + 1 = 249 trailing zeros. 50! has 10 + 2 = 12. 24! has 4, and 25! jumps to 6, because 25 brings two fives at once. That jump is a favourite follow-up: there is no factorial with exactly 5 trailing zeros.
Step 4: Making it fast
Each term is the previous term divided by 5, rounded down. For 1000: 200, then 40, then 8, then 1. Done in four quick divisions, which is the speed an interviewer expects. A quick sanity check is that the answer is always a bit under n/4, since 1/5 + 1/25 + ... = 1/4.
Interviewers sometimes vary the base: how many trailing zeros does 100! have in base 12? Then you need factors of 12 = 2² × 3, count the twos (97) and the threes (48), and take the limiting one: min(97/2, 48) = 48.
Why interviewers ask it
Say 'count the fives, not the tens' in the first sentence. The base-12 variant is the usual follow-up, so mention Legendre's formula by name.
Knowing the proof is half of it. Work Trailing Zeros of 100! interactively, then take it under a clock with the rest of the Outcry simulators.