描述

设计一个算法，计算出n阶乘中尾部零的个数

样例

样例  1:
	输入: 11
	输出: 2
	
	样例解释: 
	11! = 39916800, 结尾的0有2个。

样例 2:
	输入:  5
	输出: 1
	
	样例解释: 
	5! = 120， 结尾的0有1个。

挑战（√）

O(logN)的时间复杂度

编程语言：Java

解题思想：

1.不使用暴力枚举法，在数够大的情况会失效，并且内存使用过大。

2.每一个零的产生都是由含有2和5的数的乘法导致的，同时在一个区间中，有多少个含5个数就有多少个含2的数。

举例：5的阶乘=5*4*3*2*1=120，有1个0，其中有一个2*5。

10的阶乘=10*9*8*7*6*5*4*3*2*1=3628800，有2个0，把10拆分为2*5，则其中有两个2*5。

25的阶乘中含有2*5*10*12*15*20*22*25可以拆分为：

2*5=2*5，10=2*5，12*15=（2*5*1.2）*（2*5*1.5）=2*5*2*5*1.8，因为产生了一个非2非5的数，因此只进1位0。

20*22*25=（2*5*2）*（2*5*2.2）*（2*5*2.5）=2*5*2*5*2*5*2*5*1.1，因为产生了 一个非2非5的数，因此只进3位0.

则合并起来其中有六个2*5。

具体到算法，则不需要计算n的阶乘，可以直接根据n来计算，因为通过n即可计算出（拆分出）有多少个2*5且不含非2非5的数，我们只需要一直利用n/5，直到n/5<1为止，然后一直累计过程中得到的n/5。

举例：n=120时，120/5=24，但24还可以除5，则24/5=4，而4/5<1，则尾部有28个0。

时间复杂度：O(logN)

IDE代码如下：

package LintCode_Easy;
 
public class _2 {
 
	public static void main(String[] args) {
		//这题需要使用数学技巧，非常巧妙，如果使用计算阶乘的方法，int和long在数很大的的情况下空间不够
		//如果使用BigInteger则会导致内存超出
		//因此解题方法需要另辟蹊径
		long n = 5555550000000L;
		long zerototal=0;
		while(n>=5)
		{
			zerototal+=n/5;
			n/=5;
		}
		System.out.println(zerototal);
	}
 
}
 

LintCode编辑器代码如下：

public class Solution {
    public long trailingZeros(long n) {
        long zerototal=0;
		while(n>=5)
		{
			zerototal+=n/5;
			n/=5;
		}
		return zerototal;
    }
}