Leetcode 172. Factorial Trailing Zeroes

1. Description

2. Solution

解析：Version 1简单，容易理解，但计算量大，耗时长。Version 2是只处理最后一位为0或5的情况，因为末尾所有的0都来自于这些数字。Version 3更进一步，变为统计数字中包含因子5的个数。Version 4则是统计数字中包含因子5，52，53，…，5^n的个数。

• Version 1

代码语言：javascript复制

class Solution:
    def trailingZeroes(self, n):
        result = 1
        count = 0
        for i in range(1, n   1):
            result *= i
        s = str(result)
        i = len(s) - 1
        while s[i] == '0':
            i -= 1
            count  = 1
        return count

• Version 2

代码语言：javascript复制

class Solution:
    def trailingZeroes(self, n):
        if n < 5:
            return 0
        result = 1
        count = 0
        exp = 16
        for i in range(5, n   1, 5):
            result = result * i * exp
            while result % 10 == 0:
                count  = 1
                result //= 10
        return count

• Version 3

代码语言：javascript复制

class Solution:
    def trailingZeroes(self, n):
        count = 0
        for i in range(5, n   1, 5):
            temp = i
            while temp % 5 == 0:
                count  = 1
                temp //= 5
        return count

• Version 4

代码语言：javascript复制

class Solution:
    def trailingZeroes(self, n):
        count = 0
        while n:
            n //= 5
            count  = n
        return count

Reference

1. https://leetcode.com/problems/factorial-trailing-zeroes/

version

0 人点赞