Given an integer n
, return the number of trailing zeroes in n!
.
Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
.
Example 1:
Input: n = 3 Output: 0 Explanation: 3! = 6, no trailing zero.
Example 2:
Input: n = 5 Output: 1 Explanation: 5! = 120, one trailing zero.
Example 3:
Input: n = 0 Output: 0
Constraints:
0 <= n <= 104
Follow up: Could you write a solution that works in logarithmic time complexity?
Companies: Microsoft, Google, Amazon, Bloomberg
Related Topics:
Math
Similar Questions:
- Number of Digit One (Hard)
- Preimage Size of Factorial Zeroes Function (Hard)
- Abbreviating the Product of a Range (Hard)
- Maximum Trailing Zeros in a Cornered Path (Medium)
// OJ: https://leetcode.com/problems/factorial-trailing-zeroes
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
int trailingZeroes(int n) {
if (n == 0) return 0;
int ans = 0;
while (n >= 5) {
ans += n / 5;
n /= 5;
}
return ans;
}
};