LeetCode Factorial Trailing Zeroes

Problem

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

Note: Your solution should be in logarithmic time complexity.

即计算n!末尾0的个数。要求用对数时间复杂度

Python 实现

# Given an integer n, return the number of trailing zeroes in n!.
#
# Note: Your solution should be in logarithmic time complexity.

# author li.hzh
class Solution:
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 0
        while n >= 5:
            result += n // 5
            n = n // 5
        return result


solution = Solution()
print(solution.trailingZeroes(102))

分析

思路其实很直接，因为想出现0。就是 2 * 5（的倍数）。注意25是两个5。2足够。因此题目就变成求1 到 n。有多少个5。

然后，就是这个计算多少个5，却让我想了一段时间，确实不应该。就是就是递归的/5即可。因为第一次/5相等于计算有多少个5。再加上第二次，相当于求多少个25。第三次就是多少个125。叠加到一次，正好就是所有的5的个数。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号