[Leetcode/파이썬] 172. Factorial Trailing Zeroes

Factorial Trailing Zeroes

---

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?

 

class Solution:
    def trailingZeroes(self, n: int) -> int:
        cnt = 0 # 5의 개수
        while n > 0 :
            n //= 5
            cnt += n

        return cnt
        # * 10을 찾아라 인 문제인 것 같다. 
        # 이 문제에서는 가장 마지막 숫자에서 0이 연속적으로 얼마나 등장하는가를 보는 것 같다.
        # 다시 말해 10 이 몇번 등장하냐, 팩토리얼 에서 10 ** x에서 x를 구하는 문제.
        # 이 문제에 대해서 찾아보니까 10 = 2 * 5로 구성되어 있으며,
        # 5의 개수를 찾는 것 만으로 이 문제를 해결할 수 있다. 
        # 2는 짝수의 조건으로서, 너무 많이 등장하게 되므로 10을 찾는데 적절하지 않다고 한다.

이 문제에 대해서 구글검색에서 찾아보니

$$ f(n) = \sum_{i=1}^{k} \left\lfloor \frac{n}{5^i} \right\rfloor = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{5^2} \right\rfloor + \left\lfloor \frac{n}{5^3} \right\rfloor + \ldots + \left\lfloor \frac{n}{5^k} \right\rfloor $$

이며, $k$에 대해서는

$$ {5} ^ {k} \leq n < {5} ^ {k + 1} $$

$$ k = \lfloor {log}_{5}{n} \rfloor $$

가장 처음식을 코드로 구현하면 된다.
n 이 0이 될 때 까지 5로 나누고, k에 n을 계속 더해가면 된다. (코드 참고)