Factorial Trailing Zeroes
Medium · Math · Math
Problem
Given an integer n, return how many zeros appear at the end of n!, the product 1 × 2 × … × n (with 0! = 1).
The factorial itself grows far too fast to compute and inspect for large n. Aim for a solution whose running time grows with the number of digits of n, not with n.
Examples
Input: n = 7 Output: 1
7! = 5040: only 5 contributes a factor 5, so there is one zero.
Input: n = 26 Output: 6
The multiples of 5 up to 26 are 5, 10, 15, 20 and 25, five numbers, and 25 holds a second 5: six zeros.
Input: n = 0 Output: 0
0! = 1, which ends in no zero.
Constraints
- 0 <= n <= 10^4
Approaches
- Baseline: count the 5s in each multiple of 5 — time O(n), space O(1)
Follow-up
The same count works for any prime: the number of times a prime p divides n! is n // p + n // p² + … (the first use case). Turned around, it also answers "which is the smallest n whose factorial ends in at least k zeros?", by binary search on n (the second use case).
Related problems
Start free on Cariara · Coding problems · System design studio
