172. 阶乘后的零

题述

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

示例 1:

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

示例 2:

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

说明: 你算法的时间复杂度应为 O(log n) 。

思路（解法1——模拟）

最初的思路是计算阶乘，按照人的计算思维来模拟计算步骤，先求阶乘运算的结果再从后往前对阶乘结果中数零。

还特意选了个效率高的求阶乘orz，结果不尽人意。

def trailingZeroes(self, n: int) -> int:
    if n == 0:
        return 0
    # 求阶乘
    N2 = n
    a = list(range(1, n+1))
    while N2 > 1:
        N1 = N2 % 2
        N2 = N2//2+N1
        for i in range(N2-N1):
            a[i] *= a[N2+i]
        a = a[0:N2]
    # 对结果数零
    num = str(a[0])
    end = len(num)
    for i in range(end):
        cnt = i
        if num[end - i - 1] != '0':
            break
    return cnt

最后惨不忍睹

翻看官方题解，按照最初的思路其给出的代码如下：

def trailingZeroes(self, n: int) -> int:
        
    # Calculate n!
    n_factorial = 1
    for i in range(2, n + 1):
        n_factorial *= i
    
    # Count how many 0's are on the end.
    zero_count = 0
    while n_factorial % 10 == 0:
        zero_count += 1
        n_factorial //= 10
        
    return zero_count

由于没有优化过所以TLE了

时间复杂度小于O(n^2)，空间复杂度O(logn!)=O(nlogn)

当然还有更好的解法，

解法2——计算因数5

为了确定最后有多少个零，我们应该看有多少对 2 和 5 的因子。在一个阶乘中，我们把所有 1 和 n 之间的数相乘和把所有 1 和 n 之间所有数字的因子相乘是一样的。

例如，如果 n=16，我们需要查看 1 到 16 之间所有数字的因子。我们只对 2 和 5 有兴趣。包含 5 因子的数字是 {5，10，15}，包含因子 22 的数字是 {2、4、6、8、10、12、14、16}。只需要看最少的对有多少个，因为只有三个完整的对，即包含 5 的因子数，因此 16! 后有三个零。

由于只计算5的倍数，所以可以五步五步地迭代

def trailingZeroes(self, n: int) -> int:
    zero_count = 0
    for i in range(5, n + 1, 5):
        current = i
        while current % 5 == 0:
            zero_count += 1
            current //= 5
    return zero_count

不过这种解法还是很慢

时间复杂度O(n)，空间复杂度O(1)

解法3——高效计算因子5

不必每次尝试 5 的幂，而是每次将 n 本身除以 5。另外，可以从5开始计数。

def trailingZeroes(self, n: int) -> int:
    zero_count = 0
    while n >= 5:
        n //= 5
        zero_count += n
    return zero_count

时间复杂度O(logn)，空间复杂度O(1)

递推公式：$ res = \frac{n}{5}+\frac{(\frac{n}{5})}{5}+\frac{(\frac{(\frac{n}{5})}{5})}{5}+… $

依照上面找出的规律也可以通过递归实现，更简洁。

解法4——递归（一行代码秒杀）

def trailingZeroes(self, n: int) -> int:
    return 0 if (n < 5) else self.trailingZeroes(n//5)+n//5

python还是太慢了，用C++实现一下。

C++实现

高效计算因数5用C++再写一遍如下：

int trailingZeroes(int n) {
	int zero_conut = 0;
	while(n >= 5){
		n /=5;
		zero_conut += n;
	}
	return zero_conut;
}

改成for循环会比while快一点

int trailingZeroes(int n) {
	int zero_conut = 0;
	for (; n >= 5; n /= 5,zero_conut += n){}
	return zero_conut;
}

用递归一行代码实现

int trailingZeroes(int n) {
        return n<5?0:(n/5+trailingZeroes(n/5));
    }

leetcode给出的结果总是有点抽风，不过效率看起来不错。beat100%，好耶！