Factorial Trailing Zeroes: Counting Factors of Five

Given an integer n, return the number of trailing zeroes in n! (n factorial).

This is LeetCode 172: Factorial Trailing Zeroes. A few examples:

• n = 3 returns 0 (3! = 6, no trailing zeroes)
• n = 5 returns 1 (5! = 120, one trailing zero)
• n = 0 returns 0 (0! = 1)

The follow-up asks for an O(log n) solution. Computing n! and counting zeroes would overflow for large n and would be far too slow. The trick is to count trailing zeroes without ever computing the factorial.

The approach

A trailing zero is produced by a factor of 10 in the product. Since 10 = 2 * 5, every trailing zero requires one factor of 2 and one factor of 5 from the numbers 1 through n.

In any factorial, factors of 2 are far more plentiful than factors of 5. Every even number contributes at least one 2, but only every fifth number contributes a 5. So the number of trailing zeroes equals the number of times 5 appears as a factor in n!.

To count factors of 5:

• n // 5 counts multiples of 5 (each contributes at least one factor of 5)
• n // 25 counts multiples of 25 (each contributes an extra factor of 5 beyond what the first term already counted)
• n // 125 counts multiples of 125 (yet another extra factor of 5)
• Continue dividing by increasing powers of 5 until the divisor exceeds n

The formula is:

count = n // 5 + n // 25 + n // 125 + n // 625 + ...

Why this works

Consider n = 25. The multiples of 5 up to 25 are 5, 10, 15, 20, and 25. That is five numbers, each contributing one factor of 5. But 25 = 5 * 5 contains a second factor of 5. The first term 25 // 5 = 5 catches the first factor from all five multiples. The second term 25 // 25 = 1 catches the extra factor from 25 itself. Total: 6 trailing zeroes.

Python solution

def trailingZeroes(n):
    count = 0
    while n >= 5:
        n //= 5
        count += n
    return count

Walkthrough

Let's trace through trailingZeroes(100) step by step.

The loop runs only 3 times for n = 100. For n = 1,000,000,000, it would run just 13 times. That is the power of dividing by 5 at each step.

Complexity analysis

The loop divides n by 5 on each iteration, so it runs floor(log_5(n)) times. Each iteration does constant work. No extra data structures are needed.

Edge cases to watch for

Before submitting, make sure your solution handles these:

• n = 0: 0! = 1, which has 0 trailing zeroes. The loop body never executes since 0 < 5.
• n = 4: 4! = 24. No multiple of 5 exists in the range 1..4, so the answer is 0.
• n = 5: 5! = 120. Exactly one multiple of 5, so the answer is 1.
• n = 25: 25! has 25 // 5 + 25 // 25 = 5 + 1 = 6 trailing zeroes. Forgetting the second term is a common mistake.
• Large n: For n = 10^9, the answer is 10^9 // 5 + 10^9 // 25 + ... = 249,999,998. The loop runs about 13 times. No overflow risk in Python.

The building blocks

This problem is built on two reusable patterns:

Prime factor counting. Instead of computing a product and inspecting the result, you count how many times a prime factor appears across the inputs. This technique shows up whenever a problem asks about divisibility properties of factorials, combinations, or large products. The key insight is that you can reason about prime factors independently.

Geometric series of divisors. The formula n//5 + n//25 + n//125 + ... is a sum over powers of 5. Recognizing this as a geometric progression of divisors gives you the O(log n) loop structure. The same pattern appears when counting how many numbers in a range are divisible by powers of a prime, which is useful in problems involving GCD, LCM, or number-theoretic sieves.

From understanding to recall

You have seen why trailing zeroes come from factors of 5, how to count them with a simple loop, and why the formula works for numbers like 25 that contain multiple factors of 5. The logic is clean and short.

But under interview pressure, you need the connection between "trailing zeroes" and "count factors of 5" to surface instantly. That only happens if you have practiced the pattern enough times that the reasoning is automatic: trailing zero means factor of 10, factor of 10 means 2 times 5, more 2s than 5s, so count 5s.

Spaced repetition locks this in. You solve the problem from scratch today, again in two days, then four days, then a week. Each time, you rebuild the loop and the edge case reasoning from memory. After a few rounds, the pattern is yours.

Related posts

• Pow(x, n) - Another math problem where repeated division (halving the exponent) turns a brute-force O(n) approach into O(log n)
• Climbing Stairs - A problem where breaking a computation into smaller subproblems reveals a clean recurrence, similar to how factoring reveals the structure here