好吧，又是两分钟看完一道投机取巧的算法题

秒速五厘米 2022-02-04 06:21 204阅读 0赞

![640?wx\_fmt=png][640_wx_fmt_png]

题目来源于 LeetCode 上第 172 号问题：阶乘后的零。题目难度为 Easy，目前通过率为 38.0% 。

### 题目描述 ###

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

**示例 1:**

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

**示例 2:**

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

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

### 题目解析 ###

题目很好理解，数阶乘后的数字末尾有多少个零。

最简单粗暴的方法就是先乘完再说，然后一个一个数。

事实上，你在使用暴力破解法的过程中就能发现规律： **这 9 个数字中只有 2（它的倍数） 与 5 （它的倍数）相乘才有 0 出现**。

所以，现在问题就变成了这个阶乘数中能配 **多少对 2 与 5**。

举个复杂点的例子：

`10！ = 【 2 *（ 2 * 2 ）* 5 *（ 2 * 3 ）*（ 2 * 2 * 2 ）*（ 2 * 5）】`

在 10！这个阶乘数中可以匹配两对 2 \* 5 ，所以10！末尾有 2 个 0。

可以发现，一个数字进行拆分后 2 的个数肯定是大于 5 的个数的，所以能匹配多少对取决于 5 的个数。（好比现在男女比例悬殊，最多能有多少对异性情侣取决于女生的多少）。

那么问题又变成了 **统计阶乘数里有多少个 5 这个因子**。

需要注意的是，像 25，125 这样的不只含有一个 5 的数字的情况需要考虑进去。

比如 `n = 15`。那么在 `15!` 中 有 `3` 个 `5` (来自其中的`5`, `10`, `15`)， 所以计算 `n/5` 就可以 。

但是比如 `n=25`，依旧计算 `n/5` ，可以得到 `5` 个`5`，分别来自其中的`5, 10, 15, 20, 25`，但是在 `25` 中其实是包含 `2`个 `5` 的，这一点需要注意。

所以除了计算 `n/5` ， 还要计算 `n/5/5 , n/5/5/5 , n/5/5/5/5 , ..., n/5/5/5,,,/5`直到商为0，然后求和即可。

### 代码实现 ###

public class Solution\{  
public int trailingZeroes(int n)\{  
return n == 0 ? 0 : n / 5 \+ trailingZeroes(n / 5);  
\}  
\}

**往期热文**

[拜托，面试官别问我「布隆」了][Link 1]

[有点难度，几道和「滑动窗口」有关的算法面试题][Link 2]

**推****荐阅读**

[几道和「二叉树」有关的算法面试题][Link 3]  
[几道和「堆栈、队列」有关的面试算法题][Link 4]

[链表算法面试问题？看我就够了！][Link 5]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 6]

[如何有效的写算法题][Link 7]

来和程序员小吴一起学算法~

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

我就知道你在看！

[640_wx_fmt_png]: /images/20220204/dc07280722184cf787d6af6c5ee8c7e0.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485197&idx=1&sn=1bbd40d49adb09875fd324664bd5bc8b&chksm=fa0e688ccd79e19a36599b53e4a8acf9a725ace3f6df28925075ff25778238471a283f0f8e1f&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485214&idx=1&sn=00de6e810caa7e261b8f2e19c3acd9cd&chksm=fa0e689fcd79e189282babbe3a688158b505e7b907971eede501addac9e0bec1e9d1c77ffb78&scene=21#wechat_redirect
[640_wx_fmt_jpeg]: /images/20220204/bace15f17e2a427ba92cad10091d8a1d.png