172. 阶乘后的零

Difficulty
Medium
Tags
数学
URL
https://leetcode-cn.com/problems/factorial-trailing-zeroes/
Star
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0
提示：
  • 0 <= n <= 104
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
通过次数136,283提交次数283,825

法 1 朴素思路

思路
n的阶乘n！末尾的“0”与n！的因式分解中的因子“5”是一一对应的，证明参见 法 2.
因此，采样朴素的思路，计算每个数字中 因子 5的个数
题解
class Solution:
    def trailingZeroes(self, n: int) -> int:
        res = 0
        for i in range(0, n+1, 5):
            res += self.helper(i)

        return res

    def helper(self, num):
        res = 0
        while num and num % 5 == 0:
            res += 1
            num //= 5

        return res
时间复杂度为 nlogn

法 2 动规思路

思路
末尾 0 的个数就是指这个数总共有几个 10 因子，而 10 又能表示成 2 和 5 的乘积。假设 m=n!，那么 m 中 2 的因子个数肯定大于 5 的因子个数，所以 m 中 5 的因子个数即是所要求结果；
令 f(x) 表示正整数 x 末尾所含有的“0”的个数，则有：
  • 当0 < n < 5时，f(n!) = 0;
  • 当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。
理解：1~n中的n个数字，有 n//5 个数字 可以先 各自贡献一个 5, 然后1~N中有 1~N//(5**2) 个数，这每个数又都能贡献一个 5.
对于n的阶乘n！，其因式分解中，如果存在一个因子“5”，那么它必然对应着n！末尾的一个“0”。 下面对这个结论进行证明：
  • 当n < 5时, 结论显然成立。
  • 当n >= 5时，令n！= [5k * 5(k-1) * ... * 10 * 5] * a，其中 n = 5k + r (0 <= r <= 4)，a是一个不含因子“5”的整数。 对于序列5k, 5(k-1), ..., 10, 5中每一个数5i(1 <= i <= k)，都含有因子“5”，并且在区间(5(i-1),5i)(1 <= i <= k)内存在偶数，也就是说，a中存在一个因子“2”与5i相对应。即，这里的k个因子“5”与n！末尾的k个“0”一一对应。 我们进一步把n！表示为：n！= 5^k * k! * a（公式1），其中5^k表示5的k次方。很容易利用(1)和迭代法，得出结论1。
上面证明了n的阶乘n！末尾的“0”与n！的因式分解中的因子“5”是一一对应的。也就是说，计算n的阶乘n！末尾的“0”的个数，可以转换为计算其因式分解中“5”的个数。
题解
notion imagenotion image
class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n >= 5:
            count += n // 5
            n //= 5
        return count
class Solution:
    def trailingZeroes(self, n: int) -> int:
        if n < 5:
            return 0
        
        return n // 5 + self.trailingZeroes(n // 5)

类似题目

求N!的二进制表示中最低位1的位置。
在二进制表示中，最低位的1在那个位置，取决于有多少个因子2。因此本题转化为求1~n中因子2的个数。
因为只要出现一个 因子2，二进制最低位的1就会向左移动一位。
因此，同172. 阶乘后的零，可以采样动态规划的思想或者朴素的思路来统计1~n这n个数字中因子2的个数。
def solve(n):
    if n < 2:
        return 0
    return n // 2 + solve(n // 2)
    
def solve(n):
    res = 0
    while n:
        res += n // 2
        n = n // 2
    return res