lintcode(二)：尾部的零 【简单题】python

描述

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

要求

O(logN)的时间复杂度

思路：

n!中尾部零的个数，即有多少个10相乘 ≡ 2*5 。

而2的指数增长速度比5的指数增长速度要快，故2的个数比5多，只需要考虑5的个数 tmp=n//5 个，

但是考虑到这 tmp = n//5 个数中，又有5的倍数，还能得到10。故继续重复上一步的操作：tmp = tmp//5

以下图为例，来源：https://blog.csdn.net/nwsuaf_uestc/article/details/78788932

class Solution:
    """
    @param: n: An integer
    @return: An integer, denote the number of trailing zeros in n!
    """
    def trailingZeros(self, n):
        # write your code here, try to do it without arithmetic operators.
        count = 0
        tmp = n//5
        
        while tmp != 0 :
            count = count + tmp
            tmp = tmp//5
            
        return count