[C++] LeetCode : Factorial Trailing Zeros

Question

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

integer 변수 n이 주어졌을 때, n 팩토리얼의 traling zeros 숫자 개수를 리턴하라.

 

trailing zero란 일의 자리수 부터 있는 0의 개수이다.

예를 들어, 12300 이면 trailing zero는 2이다.

 

다만 중간에 0이 나오는 것은 trailing zero는 아니다. 

예를 들어, 1200300의 trailing zero는 2이다. 

 

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

 

제약사항

• 0 <= n <= 10⁴

---

Solution

문제를 풀 때 고려한 사항

• n이 0일때는 0! = 1이라 trailing zero는 0으로 처리해야 한다. 

---

Solution1

0이 나오는 경우를 고려해보자

0! = 1
1! = 1
2! = 2 x 1 = 2
3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120
6! = 6 x 4 x 4 x 3 x 2 x 1 = 720
...
10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 2 x 1 = 362800

보면 알수 있듯이 2의 개수와 5의 개수에 따라 0의 개수가 정해진다. 
5! = 5가 1개 2가 3개 있음으로 0의 개수는 1개이고
10! = 10가 5가 2개 2가 8개로 0의 개수는 2개이다. 

즉, 2와 5의 개수를 센다면 trailing zero의 개수를 셀 수 있다. 

그렇다면 어떤 식으로 셀 것인가. bottom up 으로 누적시켜야 할지, 아니면 해당 숫자를 기준으로 분해해야 할지 고민해봐야 한다. 

bottom-up 방식이라면 숫자 n인 경우 O(n) 의 시간 복잡도와 공간 복잡도를 가지게 될 것이다. 

해당 숫자를 기준으로 분해한다고 가정해보자. 5의 개수는 5의 배수를 기준으로 추가되는 것을 고려했을 때

5! = 5가 1개
10! = 5가 2개
15! = 5가 3개
20! = 5가 4개
25! = 5가 6개 
30! = 5가 7개
35! = 5가 8개
40! = 5가 9개
45! = 5가 10개
50! = 5가 12개

n! 의 trailing zero의 개수는 (n/5) 의 개수 + n 이하의 5의 제곱 수의 개수의 합이라 볼 수 있다.
n의 범위 0<= n <=10000 고려하였을 때, 제곱 수는 최대 5의 5승까지만 나올 수 있다.

class Solution {
public:
    int trailingZeroes(int n) {
		int radix = 5;
        int ans = 0;

		while(n >= radix && radix < 10000){
			ans += n/radix;
			radix *=5;
		}
		
		return ans;
    }
};