# 172. Factorial Trailing Zeroes 阶乘后的零

@TOC

## # 题目描述

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.

## # 题目大意

### # 递归

``````return n/5 + n/25 + n/125 + n/625 + n/3125+...;
``````

``````class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
i = 5
while n >= i:
res += n / i
i *= 5
return res
``````

### # 循环

``````public class Solution {
public int trailingZeroes(int n) {
if(n<=0)    return 0;
int count = 0;
for (long i = 5; n / i >= 1; i *= 5) {
count += n / i;
}
return count;
}
}
``````

AC:1ms

python解法如下：

``````class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
i = 5
while n >= i:
res += n / i
i *= 5
return res
``````

## # 日期

2016 年 5 月 8日 2018 年 11 月 24 日 —— 周六快乐