[Leetcode/Python] Factorial Trailing Zeroes

Top Interview Questions 의 Medium Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

 

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

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

 

Example 1:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:

Input: n = 0
Output: 0

 

Constraints:

• 0 <= n <= 104

 

Follow up: Could you write a solution that works in logarithmic time complexity?

 

Code:

#1 : 10^n의 배수인 수 찾기
class Solution:
    def trailingZeroes(self, n: int) -> int:
        num = n
        for i in range(n-1,0,-1):
            num *= i
        answer = 0
        while True:
            num, isZero = divmod(num, 10)
            if num and isZero == 0:
                answer += 1
            else:
                return answer

#2 : 5의 배수 활용
class Solution:
    def trailingZeroes(self, n: int) -> int:
        answer = 0
        while n > 0:
            n //= 5
            answer += n
        return answer