Problem
Given an integer n, return the number of trailing zeros in n! (n factorial, n! = 1 · 2 · 3 · ... · n). A trailing zero is a 0 at the end of the number; for example, 100 has two trailing zeros. Do it without computing the factorial itself, which grows very large.
Examples
n = 3 → 0 — 3! = 6 has no trailing zero.n = 5 → 1 — 5! = 120 ends in one zero.n = 25 → 6 — 25! ends in six zeros (25 contributes two factors of 5, plus one each from 5, 10, 15, 20).
Constraints
Think about it first
Hint 1
A trailing zero comes from a factor of 10, and every 10 is a 2 × 5. So the number of trailing zeros equals the number of times 10 divides the factorial — i.e. `min(count of factor 2, count of factor 5)`.
Hint 2
Among `1..n`, factors of 2 are far more common than factors of 5. So the count of 5s is always the limiting factor — you only need to count how many 5s appear in the prime factorization of `n!`.
Hint 3
Multiples of 5 each give one 5, multiples of 25 give an extra one, multiples of 125 yet another, and so on. The answer is `n//5 + n//25 + n//125 + ...` until the term becomes 0.
TL;DR
Count the factors of 5 in n! via n//5 + n//25 + n//125 + ... — O(log₅ n) time, O(1) space.
Approach 1 — Brute force (build the factorial, count zeros)
Compute n!, then strip trailing zeros one at a time.
def trailingZeroes(n: int) -> int:
fact = 1
for i in range(2, n + 1):
fact *= i
zeros = 0
while fact and fact % 10 == 0:
zeros += 1
fact //= 10
return zeros
Complexity: n! has O(n log n) digits, so the big-integer multiplications cost roughly O(n² log n) bit operations — for n = 10^4 the number has ~35000 digits. It works in Python but is wasteful, and in fixed-width-integer languages it overflows almost immediately.
A trailing zero is a factor of 10 = 2 × 5. In n! the factors of 2 outnumber the factors of 5, so the number of 10s — and thus trailing zeros — equals the number of 5s in the prime factorization. Legendre’s formula counts those: floor(n/5) + floor(n/25) + floor(n/125) + .... Multiples of 5 each contribute one 5, multiples of 25 contribute a second, multiples of 125 a third, and so on.
def trailingZeroes(n: int) -> int:
count = 0
power = 5
while power <= n:
count += n // power
power *= 5
return count
Walkthrough with n = 25:
power = 5: 25 // 5 = 5 (the multiples 5, 10, 15, 20, 25 each give a 5) → count 5.power = 25: 25 // 25 = 1 (25 gives a second 5) → count 6.power = 125: 125 > 25, loop ends.
Answer: 6, matching 25! ending in six zeros.
Complexity: O(log₅ n) iterations (the power of 5 grows geometrically), O(1) space. No large numbers are ever formed.
Common pitfalls
- Counting only multiples of 5 (
n // 5) and forgetting that 25, 125, … each contribute additional 5s.
- Trying to balance 2s and 5s explicitly — unnecessary, since 5s are always the scarcer factor.
- Overflow / performance blowup from literally computing
n! in the brute-force approach.
Pattern takeaway
Trailing zeros in a product reduce to counting a prime factor (here 5, the rarer half of 10). Legendre’s formula — summing n // p^k for increasing k — counts the exponent of a prime p in n! without ever forming the factorial. Reach for it whenever a question is really about the prime factorization of a factorial.