图解LeetCode——793. 阶乘函数后 K 个零（难度：困难）

一、题目

 f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。 例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。 给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。

二、示例

2.1> 示例 1：

【输入】k = 0
【输出】5
【解释】0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。

2.2> 示例 2：

【输入】k = 5
【输出】0
【解释】没有匹配到这样的 x!，符合 k = 5 的条件。

2.3> 示例 3:

【输入】 k = 3
【输出】 5

提示:

• 0 <= k <= 10^9

三、解题思路

根据本题的描述，知道了一个公式，即：f(x) = k，用于表示x的阶乘计算出结果后，这个值的末尾有k个0。比如：f(5)=1，因为5! = 1 * 2 * 3 * 4 * 5=120，因为120这个值末尾有1个0，所以f(5)=1。那么，如何让结果的末尾能有0呢？ 只要我们任何数值乘以10，结果就会多一个0，比如：3 * 10 = 30，20 * 10 = 200……;那么，因为10 = 2 * 5，所以我们将10再次拆分，可以拆分出2和5，也就是说，在阶乘中，所有的整数，拆分为质数后，有多少对2和5，结果就会有多少个0；那么我们就来演示一下从0！到11！，他们的拆分情况，具体如下图所示：

在上图中，我们可以看到，对于“2”来说，2、4、6、8这4个数，可以拆出6个“2”；对于“5”来说，5、10这2个数，可以拆出3个“5”；所以，通过上面的规律我们可以看出，2出现的次数是远远大于5出现的次数的，所以，我们就可以将规则简化为：“在一个数的阶乘中，5出现了n次，那么在结果中，末尾就会有n个0”。

我们继续往下分析，通过上图我们还发现了一个规律，那就是，每隔5个数，就会出现一个“5”，例如：0、5、10、15、20、25、30……，我们可以分别将其理解为0=0*5、5=1*5、10=2*5、15=3*5、20=4*5、25=5*5、30=6*5……；那么我们发现每隔5个数字（从0*5 ~ 4*5），就会出现1次5。而我们发现，当到25的时候，出现了特殊情况，也就是25可以拆分为5 * 5，那就是说，比25之前的所有数字都多出一个“5”，具体如下图所示：

那么除了25之外，还有其他特殊的吗？当然有，比如125=5*5*5，那么就相当于出现了3次5；625=5*5*5*5，那么就相当于出现了4次5；所以，我们可以得出以下结论：在以数字n进行阶乘的时候，每隔5个数，会出现一次5，每隔25个数，会出现两次5，每隔125次，会出现三次5……，以此类推。所以，假如给我们一个数字n，它到底有多少个5，那也就相当于结果的末尾有多少个0，计算公式为：n/5 + n/25 + n/125 + N/625 + ……；其实也就是：n/5 + n/(5*5) + n/(5*5*5) + n/(5*5*5*5) + ……，具体含义如下图所示：

了解了上述我们总结出的结果，那么对于这道题，我们就可以将其翻译为：能够满足某个值x（x为非负整数）的阶乘，可以出现k个5的数量。那么我们如果可以获得第一次满足5出现了k次，和第一次满足5出现k+1次，并且两者相减，结果就是满足了5可以出现k次的数量了。我们可以举例，假如求k=1，即：末尾1个“0”出现的次数，第一次满足k=1是5的阶乘，第一次满足k=2是10的阶乘，那么最终结果就是10-5=5，即：满足末尾1个“0”的数量为5（包含：5！，6！，7！，8！，9！ 一共5个）。具体详情，如下图所示：

又因为阶乘的特殊性，它计算的结果就是单调递增的，那么我们就可以通过二分法快速的计算出满足了“5”第一次出现了k次的位置是哪里了。但是，既然要用二分法查找，那么我们就需要确定查找的范围，最大的查找范围需要设置多少合适呢？我们还来看看上面我们得出的一些规律，我们曾经总结过，每5次数字过后，才会出现1次5，那么如果我们要寻找第一次出现了k次5的话，我们要查找的范围就是5k了。所以，我们的查找范围确定为[0, 5k]。比如，我们要找k=1，即：第一次5出现的位置，那么我们的查找范围就是[0, 5]；如果k=2，二分法查找的范围就是[0，10]。

但是大家有没有发现一个规律，就是这个题的答案其实不是0就是5，所以，我们其实只需要判断k的一次出现的位置是否存在即可，如果存在，那么我们直接return 5；如果不存在，则直接return 0即可。具体代码实现，请参照如下。

四、代码实现

class Solution {
    public int preimageSizeFZF(int k) {
        long start = 0L, end = 5L * k, mid;
        while(end >= start) {
            mid = start + (end - start) / 2;
            long n = 5L, nums = 0L;
            while (n <= mid) {
                nums += mid / n;
                n *= 5;
            }
            if (nums == k) return 5;
            if (nums < k) start = mid + 1;
            else end = mid - 1;
        }
        return 0;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」