Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!. Computing factorial directly is unnecessary and will overflow quickly.

Why this is worth learning

Every trailing decimal zero comes from a factor 10=2*5. Factorials supply more twos than fives, so count the exponent of five without constructing the factorial.

Before coding: one-minute experiment

Why does 25! have six trailing zeroes rather than five?

Function signature

func TrailingZeroes(n int) int

Inputs / outputs

• n: non-negative integer.
• Return: number of trailing zeros in n!.

Example

5! = 120 -> 1
10! ends with two zeros -> 2

Constraints

• 0 <= n <= 1_000_000_000

Core idea (near-solution)

Constructing n! determines many digits the question never uses. Each trailing decimal zero consumes a factor 2 and a factor 5. Factorials provide at least as many twos, so count fives instead. Multiples of 5 contribute one layer, multiples of 25 another, and multiples of 125 a third. At n=25, counting only the five multiples of 5 misses the extra contribution from 25.

Trailing zeros come from factors of 10 = 2 * 5. There are more 2s than 5s, so count how many factors of 5 appear in all numbers from 1..n.

Invariant: after dividing by 5 repeatedly, you have counted the exact number of factors of 5.

Algorithm (step-by-step)

1. Initialize count = 0.
2. While n > 0:
   • n /= 5.
   • count += n.
3. Return count.

Correctness sketch

Every multiple of five contributes at least one factor five, giving floor(n/5). Multiples of 25 contribute one additional factor, multiples of 125 another, and so on. Summing floor(n/5^k) counts each factor five exactly once by its depth. Repeatedly dividing n by five produces these terms without explicitly multiplying powers that could overflow. When the quotient reaches zero, no larger power contributes. Since factors two are at least as abundant, this exponent equals the number of complete factors ten and hence trailing zeros.

Trace (hand walkthrough)

Example input:
5! = 120 -> 1
10! ends with two zeros -> 2

Walk:
- n=5: floor(5/5)=1 -> 1 zero
- n=10: floor(10/5)=2, floor(10/25)=0 -> 2 zeros

Pitfalls to avoid

• Computing n! directly.
• Counting only n/5 and forgetting higher powers (25, 125, ...).

Debugging lens

Test immediately before, at, and after powers of five. Counting only multiples of five misses repeated factors. n=0 correctly gives zero trailing zeroes in 0!=1.

Complexity

• Time: O(log_5 n).
• Extra space: O(1).

Implementation notes (Go)

• Use integer division; no 64-bit required unless n is extremely large.

Reconstruction checkpoint

Why does 25! have six trailing zeroes rather than five?

Return to Math · Module quiz