# Factorial Trailing Zeroes【172】

Datetime:2016-08-23 01:22:56         Topic: LeetCode          Share        Original >>

### 172. Factorial Trailing Zeroes

My Submissions

Total Accepted:  45801 Total Submissions:  147715 Difficulty:  Easy

Given an integer n , return the number of trailing zeroes in  n !.

Note:  Your solution should be in logarithmic time complexity.

Credits:

Special thanks to  @ts for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

Show Similar Problems

```//思路首先：缩小问题规模找规律：1!=1,2!=2,3!=6,4!=24,5!=120,6!=720,7!=5040,8!=40320,9!=362880,10!=3628800
//草，没想出来，看了下别人家的思路：
//核心思想每一个尾巴上的0，绝对是2和5的结果
//绝对规律1：2的个数绝对比5的个数多（这很显然）
//绝对规律2：有多少个质因子5就有多少个尾巴0
//26！有多少个质因子5？5，10，15，20，25（6个）
//51！有多少个质因子5？5，10，15，20，25,30,35,40,45,50,（12个）
class Solution {
public:
int trailingZeroes(int n) {
if(n<5)
return 0;
int cnt = 0;   //求质因子5的个数

while(n/5 != 0) {
n /= 5;
cnt += n;
}

return cnt;
}
};```

Well, to compute the number of trailing zeros, we need to first think clear about what will generate a trailing `0` ? Obviously, a number multiplied by  `10` will have a trailing  `0` added to it. So we only need to find out how many  `10` 's will appear in the expression of the factorial. Since `10 = 2 * 5` and there are a bunch more  `2` 's (each even number will contribute at least one  `2` ), we only need to count the number of  `5` 's.

Now let's see what numbers will contribute a `5` . Well, simply the multiples of  `5` , like  `5, 10, 15, 20, 25, 35, ...` . So is the result simply  `n / 5` ? Well, not that easy. Notice that some numbers may contribute more than one  `5` , like  `25 = 5 * 5` . Well, what numbers will contribute more than one  `5` ? Ok, you may notice that only multiples of the power of  `5` will contribute more than one `5` . For example, multiples of  `25` will contribute at least two  `5` 's.

Well, how to count them all? If you try some examples, you may finally get the result, which is `n / 5 + n / 25 + n / 125 + ...` . The idea behind this expression is: all the multiples of  `5` will contribute one  `5` , the multiples of  `25` will contribute one more  `5` and the multiples of  `125` will contribute another one more  `5` ... and so on. Now, we can write down the following code, which is pretty short.