[리트코드 LeetCode] Factorial Trailing Zeroes (Python)

Factorial Trailing Zeroes

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/816/
• 분류: Top Interview Questions - Medium - Math

Explore - LeetCode

문제

• 주어진 정수 n에 대해 n!의 trailing zero 수를 반환하라.
• trailing zero: 후행 0의 수 - 즉 맨 뒤에 붙는 0의 수
• n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
• type n: int / rtype: int

예시

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

조건

• 0 <= n <= 10^4

Follow up

• logarithmic (log의) 시간 복잡도를 가진 알고리즘을 생각해낼 수 있는가?

풀이

단순히 팩토리얼을 직접 계산하여 10의 개수를 세는 것은 연산 결과가 너무 커지므로 시간 초과로 불가능함 - 다른 방법으로 접근해야 함

 

1. 팩토리얼에 든 소인수 2와 5의 개수 중 더 작은 것을 반환

trailing zero는 주어진 팩토리얼에 10이 몇 번 들어가느냐에 따라 결정됨 (소인수 2, 5)

2와 5가 주어진 팩토리얼에 몇개나 들어가는지 센 다음에 2와 5의 개수 중 더 작은 것을 반환하면 됨

어떻게 세느냐 - 1부터 n까지 각 숫자에 대해 2와 5 인수의 개수를 센다

단순히 2로 나눈 나머지/5로 나눈 나머지가 0일 때 카운트를 높이면 안 됨

4, 25 등 2나 5가 여러 번 들어간 경우도 있기 때문에 더 이상 2 또는 5로 나눈 나머지가 0이 아닐 때까지 나누고 카운트를 더해야 함

class Solution(object):
    def trailingZeroes(self, n):
        if n == 0:
            return 0
        num_2 = num_5 = 0
        for i in range(1, n+1):
            while i % 2 == 0:
                i /= 2
                num_2 += 1
            while i % 5 == 0:
                i /= 5
                num_5 += 1
        return min(num_5, num_2)

Time: O(n) / Space: O(1)

Runtime: 469 ms (beats 32.98%) / Memory Usage: 13.5 MB (beats 45.96%)

 

1-2. 개선안 - 5의 수만 세기

항상 2의 수가 5의 수보다 많으므로 둘 다 세서 더 작은 것을 반환할 필요 없이 애초부터 5의 개수만 세면 됨

n! = 1*...5*....10...15...20...25...5*i..n (for every i > 5)으로 볼 수 있음

n/5 는 5를 하나 가지고 있는 수의 개수 (ex. n=20이면 20/5=4, 1~20 중 5를 하나 갖고 있는 수는 5, 10, 15, 20의 4개)

n/5/5는 5를 둘 가지고 있는 수의 개수 (ex. n=25면 25/5/5=1, 1~25 중 5를 2개 갖고 있는 수는 25 1개)

…

cnt에 주어진 수를 5로 나눈 몫을 더하고 (5를 1개 가진 수의 수) 그 몫에 또 5를 나눈 몫을 더하고 (5를 2개 가진 수의 수) … 의 반복

 

예시를 통한 설명

https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/816/discuss/52371/My-one-line-solutions-in-3-languages

a concrete example n = 25:

---

25, 24, 23, 22, 21 ----- 25/5 = 5

20, 19, 18, 17, 16 ----- 20/5 = 4

15, 14, 13, 12, 11------ 15/5 = 3

10, 9, 8, 7, 6 ----------- 10/5 = 2

5, 4, 3, 2, 1 -------------- 5/5 = 1

which gives anther loop: 5, 4, 3, 2, 1 ('2' is always enough for '5' to multiply)

So: 25/5 + 5/5 = 5 + 1 = 6

---

For n = 30,

30/5 + trailingZeros(6) = 30/5 + 6/5 + trailingZeroes(1) = 30/5 + 6/5 + 1/5 + trailingZeroes(0) = 6 + 1 + 0 + 0 = 7

---

For n = 125, the second loop would be 25, 24,...,1, and the third loop 5, 4, 3, 2, 1.

So: 125/5 + trailingZeros(25) = 25 + 6 = 31

 

1-2-1. 재귀

def trailingZeroes(self, n):
	return 0 if n == 0 else n/5 + self.trailingZeroes(n/5)

Time: O(logn) / Space: O(logn) - 재귀 호출 때문

Runtime: 20 ms (beats 75.09%) / Memory Usage: 13.5 MB (beats 60.35%)

 

1-2-2. 반복문

def trailingZeroes(self, n):
	cnt = 0
	while n:
		n /= 5
		cnt += n
	return cnt

Time: O(logn) / Space: O(1)

Runtime: 15 ms (beats 92.28%) / Memory Usage: 13.5 MB (beats 45.96)