[LeetCode][Python3] 172. Factorial Trailing Zeroes

snoopybox 2018. 11. 3. 22:18

Problem :

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

My Solution :

class Solution:
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        while n:
            n //= 5
            ans += n
        return ans

Comment :

10은 2와 5의 곱으로 만들어낼 수 있으며, 2는 매 짝수마다 나오기때문에 5보다 무조건 많다. 따라서 5의 개수만 세어주면 된다. (5, 25, 125, 625, ... 을 세어주는 것이다)

위 방법은 반복문을 이용한 것이고, 아래 방법은 Recursion을 이용한 것이다.

My Solution 2:

class Solution:
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n:
            return n//5 + self.trailingZeroes(n//5)
        return 0