卖萌的弱渣

I am stupid, I am hungry.

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note:

Your solution should be in logarithmic time complexity.

Solution

n!后缀0的个数 = n!质因子中5的个数 = floor(n/5) + floor(n/25) + floor(n/125) + ....

(Factorial-Trailing-Zeroes.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        x = 5
        ret = 0
        while n >= x:
            ret += n/x
            x *= 5
        return ret