2. Trailing Zeros【easy】
2. Trailing Zeros【easy】
Write an algorithm which computes the number of trailing zeros in n factorial.
11! = 39916800, so the out should be 2
O(log N) time
解法一:
class Solution {
/*
* param n: As desciption
* return: An integer, denote the number of trailing zeros in n!
*/
public long trailingZeros(long n) {
long count = ;
for(int i = ; Math.pow(,i) <= n; i++) {
count += n / (long)Math.pow(,i);//注意强制类型转换
}
return count;
}
};
求末尾0的个数:
至于一个数阶乘的末尾有多少个0,0的个数为(其中的“/”是取整除法):
例子:1000的阶乘末尾0的个数
1000/5 + 1000/25 + 1000/125 + 1000/625
= 200 + 40 + 8 + 1
= 249(个)
原理是:
假如你把1 × 2 ×3× 4 ×……×N中每一个因数分解质因数,结果就像:
1 × 2 × 3 × (2 × 2) × 5 × (2 × 3) × 7 × (2 × 2 ×2) ×……
10进制数结尾的每一个0都表示有一个因数10存在——任何进制都一样,对于一个M进制的数,让结尾多一个0就等价于乘以M。
10可以分解为2 × 5——因此只有质数2和5相乘能产生0,别的任何两个质数相乘都不能产生0,而且2,5相乘只产生一个0。
所以,分解后的整个因数式中有多少对(2, 5),结果中就有多少个0,而分解的结果中,2的个数显然是多于5的,因此,有多少个5,就有多少个(2, 5)对。
所以,讨论1000的阶乘结尾有几个0的问题,就被转换成了1到1000所有这些数的质因数分解式有多少个5的问题。
5的个数可以用上面那个式子算出,所以1000的阶乘结尾有249个0。
至于为什么用这个式子,可以见下例:
求26的阶乘的尾部有多少个0.
26! = 1 × 2 ×3× 4 × 5 × 6 × 7 × 8 × 9 × 10 × 11 × 12 × 13× 14 × 15 × 16 × 17 × 18 × 19 × 20 × 21 × 22 ×23× 24 × 25 × 26
内有 26/5 + 26/25 = 6(个)5相乘
因为25其实可以分解成2个5相乘,而26/5只计算了一个5,因此还要再加26/25。
参考自:http://blog.csdn.net/wutingyehe/article/details/46882181
解法二:
class Solution {
public:
// param n : description of n
// return: description of return
long long trailingZeros(long long n) {
long long sum = ;
while (n != ) {
sum += n / ;
n /= ;
}
return sum;
}
};
最新文章
- 使用httpclient 调用selenium webdriver
- 虚拟机centos6.5 --hadoop2.6集群环境搭建
- JS中数组Array的用法示例介绍 (转)
- 报错:LINQ to Entities 不识别方法
- bzoj 3118: Orz the MST(单纯形)
- cisco LAN
- Golang学习 - errors 包
- UVALive 7325	Book Borders (模拟)
- js的引用顺序
- Word Amalgamation
- BUAA 更大公约数
- OpenCV之Python学习笔记
- Oracle常用查询
- 【转载】小结一下linux 2.6内核的四种IO调度算法
- c语言中的register int
- MySQL开启binlog并且保存7天有效数据
- bzoj 4832 抵制克苏恩 概率期望dp
- Eureka的基本功能和用法
- jdk源码阅读笔记-ArrayList
- java比较排序Comparable和Comparator