172. Factorial Trailing Zeroes
1. Description
Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1.
2. Example
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
3. Constraints
- 0 <= n <= $10^4$
4. Solutions
Math
Time complexity: O(logn)
Space complexity: O(1)
class Solution {
public:
int trailingZeroes(const int n) {
int factor_five_count = 0;
int number = n;
while (number > 0) {
number /= 5;
// Each division counts how many numbers contribute at least one factor of 5.
// For example:
// n / 5 counts numbers with one factor of 5 (5, 10, 15, ...).
// n / 25 counts numbers with an extra factor of 5 (25, 50, ...).
// n / 125 counts numbers with yet another factor of 5, and so on.
factor_five_count += number;
}
return factor_five_count;
}
};