lintcode2

描述

设计一个算法，计算出n阶乘中尾部零的个数
样例
11! = 39916800，因此应该返回 2
挑战
O(logN)的时间复杂度

解1：

主要求出5的幂次次数，如25的阶乘，有5   2*5  3*5 4*5 5*5   则5的幂次次数为6，即尾部零的个数为6
因为偶数*5就会尾部就可以产生零，而偶数出现的比5出现的次数一定多，比如3!=3*2*1   6!=6*5*4*3*2*1,所以值考虑5出现的次数就好，除此之外还要加上10出现的次数。

class Solution {
public:
    long long trailingZeros(long long n) {
       long long sum = 0;
        for (long long  temp = 5; temp <= n; temp+=5) 
        {
            count++;
            long long pwr = 25;
            // 判断是不是25、125、625...的倍数，并根据每次pwr的变化进行+1操作
            while (temp % pwr == 0)
             {
                count++;
                pwr *= 5;
             }
          }
                return count;
        }
};

解2：

某个数的阶乘(如101)，我要提取5,10,15,20,25……100  
即5*(1*2*3*4*5.......*20)
sum=101/5;  //(sum是零的个数和)
而(1*2*3*4*5.......*20)又可以重复上述步骤5*(1*2*3*4）
sum=sum+101/5/5;

long long sum=0;
long long tmp=n/5;
while(tmp!=0)
{
    sum+=tmp;
    tmp/=5;
}