LintCode——尾部的零
2024-08-24 09:45:34
尾部的零:设计一个算法,计算出n阶乘中尾部零的个数
样例:11! = 39916800、因此应该返回2
分析:假如你把1 × 2 ×3× 4 ×……×N中每一个因数分解质因数,例如 1 × 2 × 3 × (2 × 2) × 5 × (2 × 3) × 7 × (2 × 2 ×2) ×……
10进制数结尾的每一个0都表示有一个因数10存在。
10可以分解为2 × 5,因此只有质数2和5相乘能产生0,别的任何两个质数相乘都不能产生0,而且2,5相乘只产生一个0。 所以,分解后的整个因数式中有多少对(2,5),
结果中就有多少个0,而分解的结果中,2的个数显然是多于5的,因此,有多少个5,就有多少个(2, 5)对。 所以,讨论n的阶乘结尾有几个0的问题,就被转换成了1到n所有这些
数的质因数分解式有多少个5的问题。
1、Python
class Solution:
"""
@param: n: An integer
@return: An integer, denote the number of trailing zeros in n!
"""
def trailingZeros(self, n):
# write your code here, try to do it without arithmetic operators.
sum = 0
while n > 0:
sum += n // 5
n //= 5
return sum
2、Java
public class Solution {
/*
* @param n: An integer
* @return: An integer, denote the number of trailing zeros in n!
*/
public long trailingZeros(long n) {
// write your code here, try to do it without arithmetic operators.
long sum = 0;
while(n>0){
sum+=n/5;
n/=5;
}
return sum;
}
}
最新文章
- Java--笔记(7)
- hibernate 中createQuery与createSQLQuery两个用法
- C#基础之lock
- 多表利用DIH批量导入数据并建立索引注意事项
- 洛谷P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib
- Shell 命令--文件创建、搜索命令--总结自《Linux Shell 脚本攻略》
- CSS 基础总结
- tcpdf导出pdf数据支持中文的解决方案
- 201521123066 《Java程序设计》第四周学习总结
- PE文件详解(六)
- LCD接口和RGB介绍【转】
- js万年历,麻雀虽小五脏俱全,由原生js编写
- client,server,nginx 在使用keepAlive 专题
- 008-Python-模块
- zabbix添加对自定义无规则的关键日志文件的监控
- Linux的管道命令
- Tkinter Colors(颜色)
- Sed命令n,N,d,D,p,P,h,H,g,G,x解析3
- 【莫队算法】【权值分块】bzoj3585 mex
- nginx别名配置,状态配置,include优化
热门文章
- 为什么ConcurrentHashMap是弱一致的
- JVM内存区域划分Eden Space、Survivor Space、Tenured Gen,Perm Gen解释 (生动形象)
- 1251. 序列终结者【平衡树-splay】
- 4196. [NOI2015]软件包管理器【树链剖分】
- [SHOI2012]回家的路
- ZooKeeper学习之路 (九)利用ZooKeeper搭建Hadoop的HA集群
- 有关linqtosql和EF的区别
- ethers.js-5-Utilities
- Go语言中的常量
- mypwd的编译和测试