Factorial Trailing Zeroes
EasyMath · Adobe
Given a non-negative integer n, return how many trailing zeroes the decimal representation of n! has.
n! (n factorial) is the product 1 * 2 * ... * n, and 0! = 1. Trailing zeroes are the zeroes at the end of the number, for example 10! = 3628800 has 2.
Computing n! directly works for small n, but aim for a solution that runs in time logarithmic in n.
Example 1
- Input:
- n = 25
- Output:
- 6
- Explanation
- 25! has a factor of 5 from each of 5, 10, 15, 20 and 25, and 25 = 5 * 5 contributes a second one, for six 5s. There are plenty of 2s to pair with them, so 25! ends in 6 zeroes.
Example 2
- Input:
- n = 12
- Output:
- 2
- Explanation
- Only 5 and 10 are multiples of 5 up to 12, so 12! = 479001600 ends in 2 zeroes.
Example 3
- Input:
- n = 130
- Output:
- 32
- Explanation
- There are 26 multiples of 5, 5 multiples of 25 and 1 multiple of 125 up to 130, giving 26 + 5 + 1 = 32.
Constraints
0 <= n <= 10^4