172. Factorial Trailing Zeroes

发表于 | 分类于 | |

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

Note: Your solution should be in logarithmic time complexity.

题意：找出n!的后缀零（结尾有多少个0）。

是在高体课上想的这道题，能想到其实后缀0就是由10来的，而10又是由25来的，而能分解出2的有好多，所以问题就转变成了：*n！能分解出多少个5。

但是到了这就基本卡在这里了，想不通怎么处理可以分解出多个5的情况，比如25和50，甚至还想着打表找规律。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int trailingZeroes(int n)
    {
        int ans = 0;
        int cnt = 0;
        for (long long i = 5; n / i > 0; i *= 5)
        {
            cnt = n / i;
            ans += cnt;
        }
        return ans;
    }
};