Factorial Trailing Zeroes
Count the number of trailing zeroes in n factorial without computing the factorial directly.
Open on LeetCode ↗Intuition
The obvious plan - compute n! and count how many zeroes it ends with - overflows almost immediately, since factorials grow faster than any fixed-width integer type can hold for even modest n. The insight is that a trailing zero comes from a factor of 10, and 10 = 2 x 5, so the number of trailing zeroes equals the number of times 10 divides n! - which equals the number of complete 2-5 pairs among n!'s prime factors. Because multiples of 2 vastly outnumber multiples of 5 in any range of consecutive integers, the count of 5s is always the bottleneck, so the answer reduces to counting how many times 5 divides into n!. The one remaining trap is numbers like 25 or 125 that contain more than one factor of 5 each - counting only n // 5 misses those extras, so you sum n // 5 + n // 25 + n // 125 + ... , where each successive power of 5 catches the numbers that contribute an additional factor.
A trailing zero comes from a factor of 10 = 2 × 5, and factors of 2 are far more plentiful than factors of 5 — so the answer is just the count of 5s in n!. Summing n/5 + n/25 + n/125 + … counts multiples of 25 twice, 125 three times, which is exactly right.
Approach
Recognize the 2-5 pairing
A trailing zero requires a factor of 10 = 2 x 5. Since even numbers vastly outnumber multiples of 5 among 1..n, the count of complete 2-5 pairs is limited entirely by how many factors of 5 appear across all the numbers from 1 to n.
Sum contributions from each power of 5
For each power of 5 (5, 25, 125, ...) up to n, add n // (that power) to a running total. n // 5 counts numbers divisible by 5 at least once, n // 25 adds one more for numbers divisible by 25 (which contribute a second factor of 5), and so on.
Stop once the power exceeds n
Once 5^k exceeds n, n // 5^k is zero and contributes nothing further, so the loop terminates in O(log_5 n) steps, and the accumulated total is the exact count of trailing zeroes.
Solution & live demo
Common pitfalls
Counting only multiples of 5 once
return n // 5
while n // power > 0:
count += n // power
power *= 525 contributes two 5s, 125 contributes three. Dividing once undercounts every input from 25 upward — the higher powers each add another sweep.
Computing the factorial
f = math.factorial(n)
return len(str(f)) - len(str(f).rstrip('0'))count += n // power
n reaches 10^4, whose factorial has tens of thousands of digits — the computation and the string conversion are both enormous. Counting factors never builds the number at all.
Overflowing the power variable
while power <= n:
while n // power > 0:
In C++/Java power *= 5 eventually overflows a 32-bit int and wraps to a negative, making power <= n true again and looping. Testing the quotient instead never multiplies past the useful range.
Edge cases
0! is 1, which has no trailing zeroes; the loop never executes since 0 // 5 == 0, giving answer 0.
No multiple of 5 exists in 1..n, so every term is 0 and the answer is 0.
n // 5 = 5 catches the five multiples of 5, and n // 25 = 1 adds the extra factor that 25 itself contributes, for a total of 6.
Only O(log_5 n) powers of 5 are needed, so the count is computed without ever forming the factorial itself.