Count Trailing Zeros in Factorial of a Number

Problem Given an integer n, count the number of trailing zeros in n! without ever computing the factorial itself.

Input / Output

• Input: an integer n >= 0.
• Output: the number of trailing zeros in n!.

Constraints

• n can be as large as 10^9, so n! is astronomically large — computing it is infeasible in time and memory.
• The answer must come from factor counting alone, in roughly O(log n).

Example

• n = 10 → 2, since 10! = 3,628,800.
• n = 25 → 6, not 5 — 25 = 5² contributes two factors of 5. This is the case that catches a naive floor(n/5).
• n = 0 and n = 4 → 0.