LEETCODE ALGORITHM:172. Factorial Trailing Zeroes

发表于 更新于 分类于 Waline： 阅读次数：

题目

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

Example 1:

1
2
3
Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

1
2
3
Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

题解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int trailingZeroes(int n) {
        int ans=0;
        while(n>=5)
        {
            n/=5;
            ans+=n;
        }
        return ans;
    }
};

本题暴力法肯定是超时，算阶乘再统计0的方法完全不可行。

拿出小学数学课本发现，要想乘积出现0，那么乘数一定有2*5(10)的因数，乘数有多少10的因数，乘积就有多少0，问题就转化为了统计1-n中有能分解出多少2，5的因数，最小的即为乘积0的个数。

所有5的倍数，25的倍数，125的倍数都会有1，2，3个5的因数。

例如100！有100/5+100/25+100/125+....个0，因为除以小的因数时已经同济了一次25，50这类也是25倍数的数的一个为5的因数，所以不需要乘以系数。

为什么只统计5，而不统计2，2的倍数的数要远远多于5的倍数的数，所以与5配对的2绰绰有余。