169. Factorial Trailing Zeroes
Given a non-negative integer n, count how many zeros sit at the end of n! — the product 1 × 2 × 3 × … × n (with 0! = 1) — and return that count.
For example 5! = 120 ends in one zero, while 10! = 3628800 ends in two. Actually computing n! gets absurd fast (100! has 158 digits), so the real task is to count the zeros without ever building the product.
Can you do it in logarithmic time?
Example 1:
Input: n = 5
Output: 1
Explanation: 5! = 120, which ends in exactly one zero.
Example 2:
Input: n = 30
Output: 7
Explanation: Multiples of 5 up to 30 contribute one factor of 5 each (six of them), and 25 = 5 × 5 contributes a second — 7 in total, so 30! ends in 7 zeros.
Example 3:
Input: n = 0
Output: 0
Explanation: 0! = 1, which has no trailing zeros.
Constraints:
- 0 ≤ n ≤ 10⁴
Hints:
Every trailing zero comes from a factor of 10 = 2 × 5 inside the product. Between the 2s and the 5s, which one is scarce?
Even numbers shower the product with 2s, so the answer is just the number of 5s in n!'s prime factorization. Each multiple of 5 donates one, each multiple of 25 donates an extra, 125 another…
So the count is n/5 + n/25 + n/125 + … (integer division), which you get by repeatedly dividing n by 5 — logarithmic time, no factorial in sight.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 5
Expected output: 1