Factorial Trailing Zeroes

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

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)

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

• Invariant: after dividing by 5 repeatedly, you have counted the exact number of factors of 5.
• The formula/transform follows from number properties or monotonicity.
• Each iteration preserves the mathematical invariant.
• Thus the computed value matches the definition of the problem.

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, ...).

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.