Factorial Trailing Zeroes 续

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

Note: Your solution should be in logarithmic time complexity.

 

有了前面C里的仔细研究,python实现应该是手到擒来,突然这时候才注意到Note里已经标明了,时间复杂度在log

可见就算时间复杂度为o(n)都无法通过,更不用提前面还来两层循环遍历的

照葫芦画瓢,很容易通过,提交

class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        j = 0
        while n > 0:
            j += n / 5
            n = n / 5
        return j

结果也通过了

502 / 502 test cases passed.
Status: Accepted
Runtime: 80 ms

还想依靠python的内置模块来试试,比如math

import math
class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        return math.factorial(n)

可是提交之后,结果莫名其妙

Status: Output Limit Exceeded
Submitted: 0 minutes ago

红色的,应该是没通过,但不清楚他想要表达什么~!

发表评论