阶乘后的零

Leetcode 172. 阶乘后的零

题意

给定一个整数n， 返回n！结果尾数中零的数量。

示例一

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例二

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明

你算法的时间复杂度应为O（log n）。

分析：

1. 通过对阶乘组成的数进行质数分解，可得阶乘出现尾数为零的结果，只能由5*2所构成，而2的个数远多于5的个数，因此只需计算质数分解后5出现的个数即可。
2. 假设n=25，那么由质数分解后，出现5的数总共有5， 10， 15， 20， 25，尾数出现零的个数为6个;
3. 其中25为,因此，n=25的可以简单记为n分别除以,,,...,，结果的和。

综上，代码为：

class Solution {
public:
    int trailingZeroes(int n) {
        // 判断n是否为零，若为零则返回零，否则返回质数分解中5出现的个数。
        return n == 0 ? 0 : n/5 + trailingZeroes(n/5);
    }
};