阶乘后的零。要求用O（log n）的时间复杂度实现，取巧篇

题目：

思路:

暴力法破解，直接计算出阶乘结果，从后往前数零，只要不是零就结束

代码：

# 直接计算阶乘   大数超过时间限制
    def trailingZeroes(self, n: int) -> int:
        result = 1
        count = 0
        for i in range(1, n + 1):
            result = result * i
        for i in str(result)[::-1]:
            if i == "0":
                count += 1
            else:
                break
        return count

结果：

结果

分析：

因为计算一个数的阶乘，耗费时间巨大。
可以做一个直观的例子。


因此暴力法难以避免的会导致超时。而且并没有达到题目要求的时间复杂度，因为要对num进行一次遍历,，因此时间复杂度是o（n）

优化分析：

• 不可能去直接计算阶乘的结果看看有多少个0.
• 可以直接发现，尾数要为0，看看阶承中的数有多少个相乘后可以为10.
  比如 5！：可以2*5.
• 10！：可以2*5，1*10，其中10又可以拆分为2*5.
• 说4*5也可以，不过我们要的是最小的因数.
• 那么就转为寻找一个阶乘有多少个2和多少个5.
• 拿20！来分析：[1*10, 2*5, 4*15, 5*6] 即：[1*2*5, 2*5, 2*2*5*3, 5*2*3].
• 再来个30！：[1*10, 2*5, 4*15, 5*6, 随便一个数20, 25*8, 30随便一个数]，即：[1*2*5, 2*5, 2*2*5*3, 2*2*5, 5*5*2*2*2, 2*5*3].
• 可以看出2总是比5多，那看看多少个5是不是就是多少个0.
• 20!的结果为2432902008176640000，有4个0刚好跟有4个5相同.
• 30！265252859812191058636308480000000有7个0,刚好也有7个5，所以可以证明.
• 只需要看给定的数中有多少个5或者5的倍数就行.

优化代码：

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

优化结果

---

欢迎关注我的公众号