LintCode 尾部的零

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

样例：11! = 39916800，因此应该返回 2

挑战：O(logN)的时间复杂度

分析：此题如果采用先求出数的阶乘，再来计算求出的结果的0的个数的话，一方面时间的复杂度太高，另一方面平时的数据类型难以存储如此大的数，需要使用大整数来进行存储。因此需要另辟蹊径，从数学的角度来看待此问题。0的个数即代表的是10的个数，而10=2*5。很明显的是：在阶乘当中5所存在的个数必定是多于2的个数的。因此，我们可以说找到了多少个5就找到了多少个10,。使用100作为例子，从1~100之间会有多少个能够被5整除的数呢？通过数学归纳法可以发现是(100/5=20)个，此时是不是就结束了呢？再来看一下1~100之中的25,50,75,100这4个数，当他们同时都除以5以后发现依次是5,10,15,20，也就是说在进行一次除以5的操作之后他们之间其实还存在着5，而此次需要求取5的个数的区间刚好是上次除以5操作后的数。由此可见，这其实是应该存在于一个循环当中的，跳出循环的条件是n非零即可。

题目代码：

class Solution {
public:
    /*
     * @param n: A long integer
     * @return: An integer, denote the number of trailing zeros in n!
     */
    long long trailingZeros(long long n) {
        // write your code here, try to do it without arithmetic operators.
        long long sum=0;
        while(n){
            sum+=n/5;
            n/=5;
        }
        return sum;
    }
};