阶乘末尾0的个数

问题

https://leetcode-cn.com/problems/factorial-trailing-zeroes/

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

示例 1:

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

示例 2:

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

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

解法

阶乘结果尾数中的 0 来自于 2*5，而 2 的数量肯定比 5 多（随便一个偶数就能分出一个分解因子2），于是 0 的数量取决于分解因子 5 的数量。

5!，为 5*4*3*2*1=120，1个0，有1个分解因子5（5提供1个）。

10!，为 10*9*8*7*6*5*4*3*2*1=3628800，2个0，有2个分解因子5（10提供1个，5提供1个）。

25!，为 25*24*...*5*4*3*2*1=15511210043330985984000000，6个0，有6个分解因子5（25提供2个，20提供1个，15提供1个，10提供1个，5提供1个）。

可以发现，分解因子5来自于5的倍数。

那么可以得到这样的一个算法：

def get_tail0_count(factorial_n: int) -> int:
    result = 0
    divisor = 5
    while divisor <= factorial_n:
        result += factorial_n // divisor
        divisor *= 5
    return result


if __name__ == '__main__':
    print("5->", get_tail0_count(5))    # 5-> 1
    print("10->", get_tail0_count(10))  # 10-> 2
    print("25->", get_tail0_count(25))  # 25-> 6
    print("125->", get_tail0_count(125)) # 125-> 31

上面的是除数从小到大，也可以除数从大到小：

def get_tail0_count(factorial_n: int) -> int:
    result = 0
    divisor = factorial_n
    while divisor > 0:
        divisor = divisor // 5
        result += divisor
    return result