793. Preimage Size of Factorial Zeroes Function

Solution idea

Binary Search + Math

要点总结

1. 如何判断阶乘 x! 的结果后面跟多少个0？

   1. 阶乘本质是乘法，那么怎么相乘可以得到末尾是0？答案：分解质因数，可以知道 2 x 5 = 10
   2. 由上一条可知，x!中 2的倍数的元素 和 5的倍数的元素 可以凑一对，在结果的末尾生产0。依据这个思路，原问题就转化为：x! 中有多少个 2的倍数的元素 和 5的倍数的元素？
   3. 2的倍数的元素数量：这个很简单，任何偶数都是2的倍数，所以，x!有一半的元素都是2的倍数
   4. 5的倍数的元素数量：很显然，5的倍数的数量远少于2的倍数的数量，也就是说x!中每提取一个因子5，总会有充足的因子2与其配对。依据这个思路，问题又进一步转化为: x! 中能提取出多少个因子5？
   5. 回答上一条的问题需要明确一个难点：10, 15, 20, ...像这样的每个元素可以提取出一个5 (贡献一个末尾0); 25, 50, 75, 100, ...像这样的每个元素可以提取出两个5 (贡献两个末尾0); 125, 250, ...像这样的每个元素可以提取出三个5 (贡献三个末尾0)；以此类推。那么，难点在于像 25，50，125 这样的数，可以提供不止一个因子 5，怎么才能不漏掉呢？
   6. 注意到：25 = 5 x 5，也就是说25比5多提供一个因子5; 125 = 5 x 5 x 5 = 25 x 5, 也就是说125比5多提供两个因子5, 比25多提供一个因子5；以此类推。这样可以发现一个等差数列的关系。
   7. 我们已经熟知的操作: 对于任何一个数n, n/5得到[1, ..., n]范围内有多少个5的倍数 (i.e. 可以提取多少个因子5)。那么，可以推断，n/25得到[1, ..., n]范围内，在n/5的基础上可以额外提取多少个因子5； n/125得到[1, ..., n]范围内，在前两者的基础上又可以额外提取多少个因子5；... 以此类推，直到 5的n次幂 > x. 以此迭代，我们就计算出了所有可以提取出来的5的数量.
      • 翻译一下这个迭代计算方法：5贡献一个末尾0，25比5又额外贡献一个末尾0，125又比25再额外贡献一个末尾0。
   8. 把上面几条推演合并起来我们就可以得到计算公式: x!的末尾多少个0 = x/5 + x/25 + x/125 + ...
      • e.g. 125! 最多可以分解出 25 + 5 + 1 = 31 个因子 5，也就是说阶乘结果的末尾有 31 个 0。

2. 如何搜索末尾k个0的 x! ?

   1. 利用Binary Search搜索边界:
      • lower bound: 找最小的x使得x!有k个0
      • upper bound: 找最大的x使得x!有k个0

Resource

讲两道常考的阶乘算法题