Java [Leetcode 172]Factorial Trailing Zeroes
2024-10-21 17:39:54
题目描述:
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
解题思路:
对于阶乘而言,也就是1*2*3*...*n
[n/k]代表1~n中能被k整除的个数
那么很显然
[n/2] > [n/5] (左边是逢2增1,右边是逢5增1)
[n/2^2] > [n/5^2](左边是逢4增1,右边是逢25增1)
……
[n/2^p] > [n/5^p](左边是逢2^p增1,右边是逢5^p增1)
随着幂次p的上升,出现2^p的概率会远大于出现5^p的概率。
因此左边的加和一定大于右边的加和,也就是n!质因数分解中,2的次幂一定大于5的次幂
代码如下:
public class Solution {
public int trailingZeroes(int n) {
int res = 0;
while(n > 0){
res += n / 5;
n /= 5;
}
return res;
}
}
最新文章
- [LeetCode] 3Sum 三数之和
- SQL Server 之 GROUP BY、GROUPING SETS、ROLLUP、CUBE
- [下载] MultiBeast 6.2.1版,支持10.9 Mavericks。Mac上的驱动精灵,最简单安装驱动的方式。
- 【原】macbook不睡眠的排查与解决
- hdu 5747 Aaronson
- Android之自定义ViewGroup
- 云服务器 ECS Linux IO 占用高问题排查方法
- php smarty foreach循环注意
- 常用布局,div竖直居中
- jquery-1.10.2 获取checkbox的checked属性总是undefined
- Windows IOT
- ZooKeeper完全分布式安装和配置
- 201521123065《java程序设计》第12周学习总结
- 二叉查找树C++实现
- 关于getch()函数
- Java 学习路线之四个阶段
- common-pool2连接池详解与使用
- Delphi非官方的补丁
- 【BZOJ4408】[FJOI2016]神秘数(主席树)
- OpenCV-Python教程8-图像混合