How to Find Trailing Zeros in a Factorial
Find the number of trailing zeros in n! using the floor(n/5) + floor(n/25) formula, with a worked example and practice questions.
Expected Interview Answer
The number of trailing zeros in n! equals the number of times 10 divides n!, which equals the number of times 5 divides n! (since factors of 2 always outnumber factors of 5), computed as floor(n/5) + floor(n/25) + floor(n/125) + ... until the terms become zero.
Each trailing zero comes from one factor of 10 = 2 × 5 in the product 1×2×...×n. Because even numbers appear far more often than multiples of 5 among 1 to n, the count of factor-2s always exceeds the count of factor-5s, so the number of 10s — and hence trailing zeros — is limited entirely by the count of 5s. Simply counting multiples of 5 undercounts, though, because numbers like 25, 125, and 625 contribute more than one factor of 5 each; adding floor(n/25), floor(n/125), and so on captures those extra contributions. The sum terminates once 5^k exceeds n, since floor(n/5^k) becomes 0.
- Reduces a huge factorial computation to a handful of division-and-floor steps
- Generalizes directly to trailing zeros in any base by counting the limiting prime power
- The same Legendre-formula idea finds the exponent of any prime in n!
AI Mentor Explanation
Counting how many times a stadium’s tannoy plays a special 'century' jingle during an innings means counting how many batters reach 100 or more, but a batter scoring 200 effectively triggers the jingle logic twice as forcefully, mirroring how a number like 25 in n! doesn’t just contribute one factor of 5, it contributes two. Trailing zeros in n! come from pairing factors of 2 and 5, but since 5s are the bottleneck, you count floor(n/5) for the basic multiples, then floor(n/25) to catch numbers like 25 and 50 that silently contribute an extra 5, continuing until the divisor exceeds n.
Worked example
floor(100/5)
- = 20
floor(100/25)
- = 4
Total zeros
- 20 + 4 = 24
Step-by-Step Explanation
Step 1
Recognize the limiting factor
Trailing zeros come from pairs of 2 and 5; 5s are always scarcer, so count 5s only.
Step 2
Count basic multiples of 5
Compute floor(n/5) for the first layer of contributions.
Step 3
Add higher powers of 5
Add floor(n/25), floor(n/125), etc. for numbers contributing extra factors.
Step 4
Stop when the divisor exceeds n
Sum terminates once 5^k > n, since floor(n/5^k) = 0.
What Interviewer Expects
- Correct identification that 5s (not 2s) are the limiting factor
- Correct application of the floor(n/5) + floor(n/25) + ... formula
- Understanding why numbers like 25 and 125 contribute more than one factor of 5
- Correct termination of the summation once the power of 5 exceeds n
Common Mistakes
- Counting only floor(n/5) and missing the extra contributions from 25, 125, etc.
- Counting factors of 2 instead of factors of 5
- Stopping the summation too early, before 5^k exceeds n
- Applying the formula to the wrong base for a non-base-10 trailing-zero question
Best Answer (HR Friendly)
“Trailing zeros come from pairing a factor of 2 with a factor of 5 in the product, and since factors of 2 are always more common than factors of 5 in a factorial, the count of 5s decides the answer. I sum floor(n/5), floor(n/25), floor(n/125), and so on to account for numbers like 25 or 125 that quietly contribute more than one factor of 5, stopping once the power of 5 exceeds n.”
Follow-up Questions
- How would you find the number of trailing zeros in n! written in base 12 instead of base 10?
- How do you find the exponent of a general prime p in n! (Legendre’s formula)?
- What is the smallest n such that n! has exactly 24 trailing zeros?
- Why do factors of 2 never become the limiting factor for trailing zeros in base 10?
MCQ Practice
1. How many trailing zeros are in 50!?
floor(50/5)=10, floor(50/25)=2, floor(50/125)=0. Total = 10+2 = 12.
2. How many trailing zeros are in 20!?
floor(20/5)=4, floor(20/25)=0. Total = 4.
3. Why do we count factors of 5, not factors of 2, when finding trailing zeros in n!?
Even numbers appear more often than multiples of 5 among 1..n, so the scarcer factor of 5 limits the number of complete 2×5=10 pairs.
Flash Cards
Why do 5s, not 2s, determine trailing zeros in n!? — Factors of 2 always outnumber factors of 5 among 1..n, so 5 is the bottleneck.
Formula for trailing zeros in n!? — floor(n/5) + floor(n/25) + floor(n/125) + ... until the term is 0.
Why does 25 contribute more than 1 factor of 5? — 25 = 5×5, so it contributes two factors of 5, not one.
When does the summation stop? — Once 5^k exceeds n, since floor(n/5^k) becomes 0.