Factorial Trailing Zeroes

Question

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

Note: Your solution should be in logarithmic time complexity.

Tags

• Maths

Thought

reference: http://www.geeksforgeeks.org/count-trailing-zeroes-factorial-number/

Find the prime factors for the input n and count the frequency of 2 and 5 among these factors. The number of trailing zeroes should be equal to 2 * 5 from prime factors. Notice that the frequency of 2 is always higher than that of 5, so we only need to count the frequency of 5. Considering the corner case of 25, 125, ... The equation for calculating the frequency of 5 from the prime factors for input n can be:

floor(n / 5) + floor(n / 25) + floor(n / 125) + ...

Code

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