172. Factorial Trailing Zeroes

Problem¶

Given n, return how many trailing 0 digits are in n!.

Example:

n = 25 -> 25! ends with 6 zeros
n = 3  -> 3! ends with no zeros

Key trick¶

Count how many times 5 appears in the prime factors of all numbers from 1 to n.

Every multiple of 5 contributes one 5
Every multiple of 25 contributes an extra 5
Every multiple of 125 contributes another extra 5

So the answer is:

n // 5 + n // 25 + n // 125 + ...

Why? A trailing zero comes from one factor 10 = 2 × 5, and there are always more 2s than 5s, so count the 5s.

Trap¶

Common mistakes:

Counting only multiples of 5, which misses extra 5s from 25, 125, ...
Computing n! directly, which is too slow and huge
Counting zeros in the decimal string of n!, which is not logarithmic
Forgetting that 0! = 1, so the answer is 0

Why is it interesting?¶

It tests whether you can turn a brute-force factorial problem into a number theory counting problem.

It rewards recognizing factorization patterns
It has a very short optimal solution
It checks for edge-case thinking and interview-style optimization

Python solution¶

class Solution:
    def trailingZeroes(self, n: int) -> int:
        # Count factors of 5 contributed by multiple of 5, 25, 125, ...
        zeros = 0
        while n > 0:
            n //= 5
            zeros += n
        return zeros

Comment on my solution¶

Your idea is basically correct: you are counting how many factors of 5 appear in all numbers from 1 to n.

What you are missing is the performance angle and one small clarity issue.

Your loop visits only multiples of 5, which is good.
Your inner loop correctly adds extra counts for 25, 125, etc.
So logically, it returns the right answer.

What is not ideal:

It still iterates through every multiple of 5, so the time is about \(O(n/5 + n/25 + n/125 + \dots)\) from the repeated divisions, which is simpler to think of as \(O(n)\) in interview terms.
The optimal solution does the same counting by jumping directly with n //= 5, which is cleaner and faster: \(O(\log_5 n)\).

Why interviewers may not love your version:

It works, but it does more work than necessary.
It is counting factors by enumerating numbers instead of using the mathematical shortcut.

A clean comment on your solution would be:

# Correct idea:
# count how many factors of 5 appear in all numbers from 1..n.
# Multiples of 25, 125, ... contribute extra 5s, so this handles them too.
# The only drawback is efficiency: it scans every multiple of 5 instead of using
# the faster n //= 5 approach.

import math

## Solution

# Works
# - complexity
#   - range(0, n + 1, 5)
#   - it's the number k such 5k <= n
class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        for x in range(0,n + 1, 5):
            if x == 0:
                continue
            while x >= 5 and x % 5 == 0:
                count += 1
                x //= 5
        return count

Solution().trailingZeroes(30) # 7
Solution().trailingZeroes(25)
Solution().trailingZeroes(131)
math.factorial(15)


# Wrong Answer - 21 / 500 testcases passed
# Solution().trailingZeroes(30) -> 6 (it should be 7)
class Solution:
    def trailingZeroes(self, n: int) -> int:
        # - brut force:
        #   - we compute n! (loop)
        #   - we count right 0s by successively shifting left n! while
        #     the digit extracted is not 0
        # - instead of computing n!
        #   - count the number of 10 appearing in the n! decomposition
        #     - for instance:
        #       - 5! = 5x4x3x2x1 = 10x(4x3) -> 1
        #       - 10! = 10x9x8x7x6x5x4x3x2x1 -> 2
        #   - counting 10s in n! decomposition is counting the number of 5s
        #     - so we're looking for max k such 5^k divide n!
        #   - so how do we count these 5s (without computing n!)

        return sum(1 for _ in range(0,n + 1, 5)) - 1

math.factorial(30) # 265252859812191058636308480000000 (7 0s)
list(range(0,31, 5)) # [0, 5, 10, 15, 20, 25, 30]
# It seems that 25 = 5x5 should be counted twice

# Works - but not log complexity
class Solution:
    def trailingZeroes(self, n: int) -> int:
        # - brut force:
        #   - we compute n! (loop)
        #   - we count right 0s by successively shifting left n! while
        #     the digit extracted is not 0

        fact_n = math.factorial(n)
        count = 0
        continue_counting = True

        while continue_counting:
            fact_n, digit = divmod(fact_n, 10)
            if digit == 0:
                count += 1
                continue
            continue_counting = False
        return count

math.factorial(10)
Solution().trailingZeroes(10)