LintCode| 尾部的零 - LintCode

接下来狂刷算法了，被打击很彻底，不就是算法吗，有嘛不会的！！！！！

1.问题：

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

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

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

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

1.算法思路：

算的数，后缀有0，则肯定是5*2的来的，又因为在阶乘中，2的倍数的出出现次数权重大于5的，所以只要含一个5因子，就会有一个后缀0
，所以就要计算出有含5因子的数量！！！

class Solution {
public:
    /*
     * @param n: A long integer
     * @return: An integer, denote the number of trailing zeros in n!
     */
    
    // 基本的思路就是，10的出现都是由于2*5算出来的，
    //又因为2的个数一定多于5的个数，所以只需要计算出含5的因子有多少，例如：
    // 20 = 4 * 5,说明20中含有4个5，也就是说明在20！的阶层中一定有4个含有5的运算因子
    // 25 = 5*5  ，sum += 5, 但是5本省还可以作为因子1*5，所以sum=6
     
     
    long long trailingZeros(long long n) {
        // write your code here, try to do it without arithmetic operators.
        long long index = 0;
        while(n!=0){
            index += (n/5);
            n /= 5;
        }
        
 
        return index;
        
    }
};