251. Trailing Zeros
A warehouse robot prints the exact value of n! (the product 1 x 2 x ... x n, with 0! = 1) in base ten on a label, and the label printer needs to know how many 0 characters sit at the very end of that number before it can choose a font size. The number itself is far too large to build.
Given the integer n, return how many trailing zeros the decimal representation of n! has. Every trailing zero comes from a factor of 10, so think about which prime factors limit how many tens you can form. Your solution should run in logarithmic time and use constant extra space.
Example 1
- Input:
- n = 137
- Output:
- 33
- Explanation:
137! contains 27 + 5 + 1 = 33 factors of five, and plenty of twos, so it ends in 33 zeros.
Example 2
- Input:
- n = 6250
- Output:
- 1562
- Explanation:
6250 gives 1250 + 250 + 50 + 10 + 2 = 1562 factors of five.
Example 3
- Input:
- n = 4
- Output:
- 0
- Explanation:
4! = 24 has no factor of five, so there are no trailing zeros.
Constraints
0 ≤ n ≤ 109
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)