Factorial Trailing Zeroes
Last Updated: March 28, 2026
Understanding the Problem
We need to count how many trailing zeroes appear at the end of n!. A trailing zero is a zero at the rightmost end of a number. For example, 120 has one trailing zero, and 1000 has three.
The naive instinct might be to compute n! and then count the zeroes at the end. But factorials grow astronomically fast. 20! is already over 2 billion, and 100! has 158 digits. So computing the full factorial is impractical for large n. We need a mathematical shortcut.
The key observation is this: a trailing zero is produced by a factor of 10, and 10 = 2 x 5. So the number of trailing zeroes equals the number of times 10 divides into n!, which equals the number of (2, 5) pairs in the prime factorization of n!. Since there are always more factors of 2 than 5 in a factorial (every even number contributes a 2, but only every fifth number contributes a 5), the bottleneck is the number of factors of 5.
Key Constraints:
0 <= n <= 10^4→ With n up to 10,000, even an O(n) approach is fine. But the follow-up asks for O(log n), which means there is a much more elegant mathematical solution.ncan be 0 → Edge case where 0! = 1, which has zero trailing zeroes.
Approach 1: Brute Force (Count Factors of 5 for Each Number)
Intuition
Since trailing zeroes come from factors of 10 = 2 x 5, and factors of 2 are always more abundant than factors of 5 in a factorial, the number of trailing zeroes equals the number of times 5 appears as a factor across all numbers from 1 to n.
The straightforward approach: iterate through every number from 1 to n, and for each number, count how many times 5 divides it. Sum those counts up.
For example, in 10!, the numbers 5 and 10 each contribute one factor of 5, so the total is 2. In 25!, the number 25 contributes two factors of 5 (since 25 = 5 x 5), while 5, 10, 15, and 20 each contribute one, giving us 6 total.
Algorithm
- Initialize a counter
count = 0. - For each number
ifrom 1 ton: - While
iis divisible by 5, divideiby 5 and incrementcount. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(n log_5(n)). We iterate through n numbers, and for each number, the inner while loop runs at most log_5(n) times (since we keep dividing by 5).
- Space Complexity: O(1). Only a few integer variables are used.
We are iterating through every single number from 1 to n, even though 80% of them are not divisible by 5 at all. Instead of checking each number individually, can we directly count how many factors of 5 exist across the entire range at once?
Approach 2: Optimal (Divide by Powers of 5)
Intuition
Here is the key mathematical insight. Instead of iterating through every number and counting its factors of 5, we can count all factors of 5 in n! at once using a simple formula.
Think about it this way:
- How many numbers from 1 to n are divisible by 5? That's
floor(n/5). Each one contributes at least one factor of 5. - How many are divisible by 25 (= 5^2)? That's
floor(n/25). Each of these contributes an extra factor of 5. - How many are divisible by 125 (= 5^3)? That's
floor(n/125). Each contributes yet another extra factor. - Keep going until the power of 5 exceeds n.
So the total number of trailing zeroes is: floor(n/5) + floor(n/25) + floor(n/125) + floor(n/625) + ...
This is sometimes called Legendre's formula for counting the power of a prime p in n!.
Every second number is even, so factors of 2 are always more abundant than factors of 5. The count of (2, 5) pairs is limited by the scarcer factor, which is always 5.
Algorithm
- Initialize
count = 0. - While
n >= 5: - Divide n by 5 (integer division).
- Add the result to
count. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(log_5(n)). We divide n by 5 in each iteration, so the loop runs log_5(n) times. For n = 10,000, that is about 6 iterations.
- Space Complexity: O(1). Only two integer variables are used.