Factorial Trailing Zeroes【172】

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

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
Math

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.





About List