[LeetCode] Fatorial Trailing Zeros 파이썬 (dp)

cache = {}

class Solution:
    def factorial_recursive(self,n):
        global cache

        if n in cache:
            return cache[n]
        
        elif n <= 1:
            return 1
        else:
            cache[n] = n * self.factorial_recursive(n-1)
            return cache[n]

        return n * factorial_recursive(n-1) if n > 1 else 1
    
    def get_zeros(self, ls):
        ls = list(str(ls))[::-1]
        cnt = 0
        for num in ls:
            if num == "0":
                cnt += 1
            else:
                break
        return cnt
    
    def trailingZeroes(self, n: int) -> int:
        if n == 0:
            return 0
        else:
            ans = self.factorial_recursive(n)
            ans = self.get_zeros(ans)
            return ans

DP로 Factorial을 구하는 메서드를 만들고

list str and reversed 로 역순으로 정렬한뒤 0이 아닐때까지 cnt

 

아주 느림

 

---

다른 풀이

# sample 24 ms submission

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