首页 » 编程之美 » 正文

[leetcode_172]Factorial Trailing Zeroes

计算n!的尾部有多少个连续的0,实际上问题可以准换为,分解质因数后,有多少个5(因为2比5多)。但是计算机5的时候有技巧,如果直接每个数模的话会超时,实际上只需要计算5^k次与n的关系即可。

class Solution {
public:
    int trailingZeroes(int n) {
        vector<int> five(14);
        for (int i = 1;i <= 13; i++)
        {
            five[i] = ((int)pow(5.0, i));
        }
        int before = 0;
        int count = 0;
        for (int i = 13; i >= 1; i--)
        {
            if( five[i] <= n)
            {
                count += (n / five[i] - before) * i;
                before = (n / five[i]);<br />
            }
        }
        return count;
    }
};

发表评论