首页 > 代码库 > leetcode 172. Factorial Trailing Zeroes

leetcode 172. Factorial Trailing Zeroes

题目描述:

技术分享

n! 的结果中,尾部有多少个0;

 

n! : n的阶乘可以看成质因数的分解 = 2k*3n*5m  结果尾部0的个数 可以看做 质因数分解后2和5的能组成的对儿的对数,即 min(k,m) ;因为一个数能被2除尽的概率比能被5除尽的概率大,所以直接统计质因数分解后5的指数是多少。

 

class Solution {
public:
    int trailingZeroes(int n) {
        int ret = 0;
        while(n){
            ret += n/5;
            n = n/5;
        }
        return ret;
    }
};

 

leetcode 172. Factorial Trailing Zeroes