Given an integer n, return the number of trailing zeroes in n!.
Follow up: Could you write a solution that works in logarithmic time complexity?
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
Idea:
All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.
4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.
5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.
9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.
10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)
What about 100! then?
100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.
Is the number of trailing zero 20? No, it’s 24, why?
Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.
So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …
Summing those numbers up we got the answer.
e.g. 1000! has 249 trailing zeros:
1000/5 = 200
1000/25 = 40
1000/125 = 8
1000/625 = 1
200 + 40 + 8 + 1 = 249
Solution:
/**
* @param {number} n
* @return {number}
*/
var trailingZeroes = function(n) {
return n < 5 ? 0 : parseInt(n / 5) + trailingZeroes(parseInt(n / 5));
};