Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count trailing zeros in n! WITHOUT computing n! (which overflows almost immediately). A trailing zero comes from a factor of 10 = 2 × 5, and 5s are far rarer than 2s, so the answer is the number of times 5 divides n!. Sum n/5 + n/25 + n/125 + … — that counts every multiple of 5, plus an extra for each multiple of 25, 125, etc. O(log₅ n) time.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you realize you must NOT compute n! (it overflows instantly), can reduce 'trailing zeros' to 'factors of 10' to 'factors of 5', and can count those factors correctly including the higher powers (25, 125, …).
Where candidates slip
Trying to compute n! then count zeros (overflows past 20!), or counting only n/5 and forgetting that 25, 125, … each add extra 5s.
How to stand out
Explain the 2×5 = 10 reduction, justify why 5s are the limiting factor, and recall the n/5 + n/25 + … summation as Legendre's formula — then note it generalizes to counting any prime's exponent.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewTrailing zeros of n!Which is scarcer?2s are plentifulExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Count Multiples of 5 (Naive)
1Hint 1Explore hintHide hint
Don't compute n! — it overflows fast. A trailing zero comes from a factor of 10 = 2×5. Which prime is rarer in n!, 2 or 5?
2Hint 2Explore hintHide hint
Since 2s outnumber 5s, count factors of 5. A first attempt: count every multiple of 5 up to n by iterating 5, 10, 15, …, n.
3Hint 3Explore hintHide hint
But careful — 25, 50, 75, 100 each contain MORE than one factor of 5. This loop, if it only counts each multiple once, undercounts. You need to divide out all the 5s from each term.
A · Core idea
Start from the right reduction: trailing zeros come from factors of 10, 10 = 2 × 5, and 5s are scarcer than 2s in n!, so we count factors of 5. The naive way is to walk every multiple of 5 from 5 up to n and tally its 5s.
Getting the reduction right is the hard part. Many candidates first write 'count the multiples of 5', i.e. just n / 5. That's correct for n < 25 but quietly wrong afterward: 25 = 5² carries two factors of 5, 125 = 5³ carries three. So the loop must, for each multiple, divide out 5 repeatedly until it no longer divides — only then have you counted all of that term's 5s.
Why this is still not what we ship. Even done correctly, iterating over all n/5 multiples is O(n) work. For n = 10⁴ that's ~2000 iterations — fine here, but the follow-up explicitly asks for logarithmic time. The key realization is that we're double-counting structure: the count of numbers ≤ n divisible by 5 is n/5, divisible by 25 is n/25, by 125 is n/125, and so on. Summing those directly gives the same total without visiting each multiple. That collapse from O(n) to O(log₅ n) is the next approach.
Why 5s and not 2s, restated. Between any 5 consecutive integers there's at least one multiple of 2 in every pair but only one multiple of 5 in five. Concretely, 10! has eight factors of 2 but only two factors of 5 — so only two (2,5) pairs, hence two trailing zeros. The 2s are never the bottleneck; counting 5s alone is exact.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 255
one 5
count = 16C · Code with teaching comments
Reference implementation previewpublic int trailingZeroes(int n) { int count = 0; for (int i = 5; i <= n; i += 5) { int multiple = i; while (multiple % 5 == 0) {Explore the full codeHide the full code
D · Why it works and complexityO(n / 5) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The whole problem hinges on one reframing: trailing zeros = (2,5) pairs = factors of 5, because 2s always outnumber 5s. The naive loop nails that reframing but pays O(n); recognizing that 'multiples of 5, then 25, then 125' can be summed directly is what unlocks logarithmic time.
ComplexityO(n / 5) time, O(1) space — Iterating over multiples of 5 up to n is O(n/5) = O(n) steps; for each we strip factors of 5. Correct if you strip fully, but still linear in n.
E · Edge cases and pitfalls5n = 4 — Loop never runs (no multiple of 5 ≤ 4); returns 0 — matches 4! = 24.Explore edge casesHide edge cases
Edge cases handled
n = 4Loop never runs (no multiple of 5 ≤ 4); returns 0 — matches 4! = 24.n = 2525 contributes two 5s via the inner while; total 6, not 5.
Pitfalls
- Counting each multiple once (just n/5) — undercounts 25, 125, ….
- Computing n! and counting zeros — overflows past 20!.
- Forgetting the inner loop strips MULTIPLE 5s per term.
Approach 2 of 2 · Optimal
Legendre's Formula — Divide by Powers of 5 (Optimal)
1Hint 1Explore hintHide hint
Instead of visiting each multiple, count them in bulk: how many integers ≤ n are divisible by 5? By 25? By 125?
2Hint 2Explore hintHide hint
Numbers divisible by 5 contribute one 5 each (n/5 of them). Those also divisible by 25 contribute a SECOND 5 (n/25 of them). By 125, a third (n/125), and so on.
3Hint 3Explore hintHide hint
So the answer is n/5 + n/25 + n/125 + … Stop when the divisor exceeds n. Implement by repeatedly dividing n by 5 and adding the quotient — O(log₅ n).
A · Core idea
The leap from the naive loop is to count in tiers instead of one number at a time. How many integers in [1, n] are divisible by 5? Exactly ⌊n/5⌋. Each of those donates (at least) one factor of 5 to n!. But the ones also divisible by 25 donate a second 5 we haven't counted yet — there are ⌊n/25⌋ of them. Those divisible by 125 donate a third — ⌊n/125⌋ — and so on. Summing ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … counts every factor of 5 exactly once. This is Legendre's formula for the exponent of a prime in a factorial.
Why each tier adds exactly the right amount. Picture the factor-of-5 count as layers. A number like 25 should contribute two 5s. It gets counted once in the n/5 tier (it's a multiple of 5) and once more in the n/25 tier (it's a multiple of 25) — total two, exactly right. 125 is counted in the /5, /25, and /125 tiers — three times, exactly its three factors of 5. The tiered sum automatically gives each number credit for every power of 5 it contains, with no double-counting and no omissions.
Why 5 is the only prime we count. A trailing zero is a factor of 10 = 2 × 5, so each zero needs one 2 and one 5. In n! the factors of 2 vastly outnumber the factors of 5 (every even number gives a 2; only every fifth number gives a 5). So the number of (2, 5) pairs is capped by the rarer prime, the 5. Counting 5s alone gives the exact number of trailing zeros — counting 2s would be wasted work since we'd always have spares.
The clean implementation and its cost. Rather than tracking divisors 5, 25, 125, … explicitly, just keep dividing n itself by 5 and accumulate: after n //= 5 the running n equals ⌊original/5⌋, then ⌊original/25⌋, and so on — adding each gives the same sum. The loop runs until n hits 0, which takes log₅ n steps. For the largest input n = 10⁴ that's about six iterations — genuinely logarithmic, satisfying the follow-up, and impossible to overflow since we never build n!.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 100Interactive diagram
Tiered counting for n = 100
startEach tier counts numbers with one more factor of 5; the tiers sum to 24.
24C · Code with teaching comments
D · Why it works and complexityO(log₅ n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Legendre's formula — Σ ⌊n/5ᵏ⌋ — is the bulk-counting version of the naive loop: each tier k credits every number that has at least k factors of 5, so the layers sum to the exact exponent. Replace 5 with any prime p and you have the general tool for counting p's exponent in n!, which underlies binomial-coefficient divisibility and Kummer's theorem.
ComplexityO(log₅ n) time, O(1) space — Each iteration divides the running value by 5, so it runs ~log₅(n) times. For n = 10⁴ that's ~6 iterations. Constant extra space → O(1).
E · Edge cases and pitfalls6n = 0 — 0! = 1; loop condition 0 > 0 is false, returns 0 immediately.Explore edge casesHide edge cases
Edge cases handled
n = 00! = 1; loop condition 0 > 0 is false, returns 0 immediately.n = 4n/5 = 0 on the first pass; loop ends, returns 0 — matches 4! = 24.n = 3030/5 = 6, 6/5 = 1, 1/5 = 0 → 6 + 1 = 7 trailing zeros.
Pitfalls
- Using `n / 25` with a fixed divisor that overflows for huge n — dividing n itself by 5 each pass avoids any overflow.
- Stopping after just `n / 5` — misses the 25, 125, … tiers.
- Counting factors of 2 instead of (or in addition to) 5 — 2s are never the bottleneck.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int trailingZeroes(int n) { int zeros = 0; while (n > 0) { n /= 5; zeros += n;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Computing the factorial directly
n! overflows a 64-bit long past n = 20. You can never materialize it; you must count prime factors instead.
Explore the code comparisonHide the code comparison
Computing the factorial directly
n! overflows a 64-bit long past n = 20. You can never materialize it; you must count prime factors instead.
Don't write this
long fact = 1;
for (int i = 2; i <= n; i++) fact *= i; // overflows past 20!
int zeros = 0;
while (fact % 10 == 0) { zeros++; fact /= 10; }Write this instead
int zeros = 0;
while (n > 0) {
n /= 5;
zeros += n;
}2Only counting n/5
Multiples of 25, 125, … carry extra factors of 5. Stopping at n/5 undercounts: for n = 25 it gives 5 instead of 6.
Explore the code comparisonHide the code comparison
Only counting n/5
Multiples of 25, 125, … carry extra factors of 5. Stopping at n/5 undercounts: for n = 25 it gives 5 instead of 6.
Don't write this
return n // 5Write this instead
zeros = 0
while n > 0:
n //= 5
zeros += n
return zeros3Fixed power-of-5 divisor overflows
Maintaining an explicit divisor that you multiply by 5 each loop can overflow for large n. Dividing n itself by 5 keeps every value small.
Explore the code comparisonHide the code comparison
Fixed power-of-5 divisor overflows
Maintaining an explicit divisor that you multiply by 5 each loop can overflow for large n. Dividing n itself by 5 keeps every value small.
Don't write this
int zeros = 0;
for (long p = 5; p <= n; p *= 5) { // p can overflow
zeros += n / p;
}Write this instead
int zeros = 0;
while (n > 0) {
n /= 5;
zeros += n;
}Revise
Carry the pattern into the interview
Pattern to remember
Count factors of 5 (Legendre's formula)
Code pattern to memorize
zeros = 0
while n > 0:
n //= 5
zeros += n
return zeros
# = n/5 + n/25 + n/125 + ...Rules to remember
- 1A trailing zero = a factor of 10 = one 2 × one 5. Count pairs of (2, 5) in n!'s prime factorization.
- 25s are the bottleneck — there are always at least as many 2s as 5s in n!, so the count of 5s alone determines the answer.
- 3Multiples of 25 contribute TWO 5s, 125 contribute THREE, etc. That's why you keep dividing: n/5 catches the first 5, n/25 catches the second, and so on.
- 4Never compute n! directly — it overflows a 64-bit long past n = 20. Count factors instead.
- 5Loop `n //= 5` and add — each iteration shifts down one power of 5; stop when n reaches 0. This is O(log₅ n), not O(n).
Use this pattern when
- Counting trailing zeros / a specific digit in a factorial or large product
- Counting how many times a prime p divides n! (Legendre's formula)
- Any 'how many factors of k' question where computing the product is infeasible
- Combinatorics divisibility (binomial coefficients mod a prime power)
Choose another pattern when
- n is tiny and the factorial fits in range → you could just compute it (but the factor count is still cleaner)
- You need the trailing zeros of an arbitrary product, not a factorial → factor each term
- Base isn't 10 / divisor isn't a prime power → generalize to per-prime counts
- You need the full value of n!, not just its zeros → big-integer arithmetic
Interview takeaway
The trick is reframing 'trailing zeros' as 'how many times does 10 divide n!', then 'how many times does 5 divide n!' since 5s are scarcer than 2s. Summing n/5 + n/25 + … is Legendre's formula — the canonical way to count a prime's exponent in a factorial, and it generalizes to any prime p.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternLegendre's formula — counting the exponent of a prime p in n! as Σ⌊n/pᵏ⌋. Recognise it whenever a question asks how many factors of some prime (or how many trailing zeros in some base) a factorial has, or for divisibility of binomial coefficients. Reframe trailing zeros → factors of 10 → factors of the scarcer prime (5), then sum the tiers.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Preimage Size of Factorial Zeroes FunctionComing soonBinary-search for n given a target trailing-zero count — the answer is always 0 or 5.
- Number of Digit OneComing soonAnother digit-counting-by-place-value problem solved with per-tier arithmetic, not enumeration.
- Permutation SequenceComing soonUses factorial number system — same comfort with factorials without computing huge values.
- Pow(x, n)Another 'don't do it the brute way' math problem — exploit structure for a log-time answer.