My python solution and explanation of log5(n) time complexity


  • 0
    Z

    Each trailing zero consists a couple of factor 2 and factor 5. Consider the number of factor 2 is enough in factorial , we can conclude that:
    For each number in factorial, if it doesn't have factor 5, it is irrelevant to trailing zeroes.
    So we can ignore those number without factor 5.

    For example,the factorial 49 becomes:
    5 * 10 * 15 * 20 * 25 * 30 * 35 * 40 * 45

    it equals:
    (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9) * (5 ** 9)

    which means that:
    trailingZeroes(49) = 49/5 + trailingZeroes(49/5)

    In more general cases:
    trailingZeroes(n) = n/5 + trailingZeroes(n/5)

    So we can do this with cycle or iteration and this is my solution of cycle version:

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.