# 172. Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
Example 1:
Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.
Example 2:
Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.
Note: Your solution should be in logarithmic time complexity.
# Solution
Approach 1: The sum of number of five in each element.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
// Time Limit Exceeded.
class Solution {
public:
int trailingZeroes(int n) {
int numOfTrailingZero = 0;
for (int i = 1; i <= n; ++i)
{
int numOfFive = 0;
int number = i;
while (number > 0 && number % 5 == 0)
{
numOfFive++;
number = number / 5;
}
numOfTrailingZero += numOfFive;
}
return numOfTrailingZero;
}
};
class Solution {
public:
int trailingZeroes(int n) {
int numOfTrailingZero = 0;
for (long base = 5; base <= n; base *= 5)
{
numOfTrailingZero += n / base;
}
return numOfTrailingZero;
}
};