LeetCode 第 172 号问题：阶乘后的零
source link: https://www.cxyxiaowu.com/6912.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文首发于公众号「五分钟学算法」，是图解 LeetCode 系列文章之一。
题目来源于 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);
}
}
Recommend
-
10
Issue #172 05 Nov 2020 Written by: Kristaps Grinbergs The last two weeks have been very active. Swift core team shared an article explaining
-
12
讲两道常考的阶乘算法题 👆让天下没有难刷的算法！若 GitBook 访问太慢，可尝试
-
6
Privacy features in Android 12 Preview Mode Links will not work in preview mode ...
-
6
在编程中函数有一个神奇又难理解的功能，就是递归。递归就是在一个过程中要调用上一步或上几步的结果，使用递归过程的函数就叫递归函数。简单说就是函数自身调用自身（听着有点反自然，像自己举起自己）。 除了数学的复杂运算中，生活中也有不少递归...
-
5
Issue #172 05 Nov 2020 Written by: Kristaps Grinbergs The last two weeks have been very active. Swift core team shared an article explaining
-
3
Macos Docker container连接宿主机172.17.0.1的办法 发表于...
-
7
Brought to you by The term “foundation” model has been around since about the middle of last year when a research group at Stanford published the comprehensive report
-
7
菜鸟收入172.92亿元，70%来自外部客户 原创 蓝鲸财经 杨泽世 · 2022-08-05 01:05:06 阅 3.9w 菜鸟相关工作人员向记者表示，菜鸟本季度进一步提升了面向商家和消费者的履约及增值服务，包括以直营配送...
-
6
js中实现阶乘（多种方法）以及阶乘求和 精选 原创 wx5dd4a114ae67d 2022...
-
9
阶乘、二分查找法及原理--分支循环的简单应用 精选 原创 光轮2000 2022-10-18 16:...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK