首页 > 代码库 > LeetCode—Factorial Trailing Zeroes

LeetCode—Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

题目是非常简单的,计算一个数字递归相乘后末尾0的个数

在相乘出现2*5才有可能出现0,2一般是足够的,主要是5的个数,因为是阶乘,比如所以只要数字大于15,那么必定经过15,10,5那么肯定包含3个以上的5,比如25,那么肯定包含25,20,15,10,5,因为25中包含5*5所以还要计算25/5中的5的个数

下面是自己最开始写的方法,虽然运行没有错,但是时间复杂度太大,不好:

int trailingZeroes(int n) {
	if(0 == n)
	{
		return 0;
	}
	int count;
	int src;
	int returnVal = 0;
	while(n)
	{
		src = http://www.mamicode.com/n;>
下面是一些简单的哦算法:
int trailingZeroes(int n) {  
	int res = 0;  
	while(n)  
	{  
		res += n/5;  
		n /= 5;  
	}  
	return res;  
} 

int trailingZeroes(int n) {
    return n < 5 ? 0 : n / 5 + trailingZeroes(n /5);
}


LeetCode—Factorial Trailing Zeroes