[LeetCode] 172. Factorial Trailing Zeroes (Python)

유빈·2025년 3월 7일

leetcode

LeetCode - Top Interview 150

목록 보기

12/13

Top Interview 150

172. Factorial Trailing Zeroes

Medium

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

class Solution(object):
    def trailingZeroes(self, n):
        num = 1
        ans = 0
        for i in range(n, 0, -1):
            num *= i
        
        for j in reversed(list(str(num))):
            if j == '0':
                ans += 1
            else:
                return ans

Time Complexity

O(N \, log N)

n! 계산 : $O(N)$
str(num) : $O(N \, logN)$
- n!의 자릿수는 $O(N \, logN)$ 정도이다.
0을 세는 과정 : $O(N \, logN)$

유빈

🌱

이전 포스트

[LeetCode] 66. Plus One (Python)

다음 포스트