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.
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
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.