Factorial Trailing Zeroes — InterviewPrepKit

Solving tips

A trailing zero is a factor of 10 = 2 x 5; since factors of 2 are far more plentiful, the count of 5s is the limiting factor.
Use Legendre's formula: answer = n//5 + n//25 + n//125 + ... until the term hits 0.
Don't forget higher powers of 5: multiples of 25 contribute a second 5, multiples of 125 a third, and so on.
Never build n! itself; the formula runs in O(log_5 n) time and O(1) space.

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 actually computing the (astronomically large) factorial.

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

0 <= n <= 10^4

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)

The literal reading: compute n!, then strip trailing zeros one at a time.

class Solution:
    def trailingZeroes(self, 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.

Approach 2 — Count factors of 5 (Legendre’s formula)

The insight: a trailing zero is a factor of 10 = 2 × 5. In n! the factors of 2 vastly 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.

class Solution:
    def trailingZeroes(self, 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.