[leetcode 172] Factorial Trailing Zeroes

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

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

 

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:

• 1 <= n <= 104

문제 풀이:

난이도 쉬움

핵심은 10을 몇개 만들 수 있느냐 이다. n!에서 소인수 분해 했을 때 2와 5의 개수가 관건이라는 의미다. 

min(2 num, 5 num)이 답인데 항상 5의 수가 더 작을 것이다.

 

따라서 5의 개수를 세준다. 1부터 n까지 5의 배수를 카운트 + 5의 제곱수를 카운트 한다.

만약 n이 25라면

1부터 n까지 5의 배수 : 5 10 15 20 25 -> 5개

+ 

25는 5의 제곱 -> 1개

 = 총 6개 이다.

 

따라서 n>0일때까지

n /= 5;

result += n;

을 해준다.

 

class Solution {
public:
    int trailingZeroes(int n) {
        if(n == 0){
            return 0;
        }
        
        int num = 0;
        while(n > 0){
            n/=5;
            num+=n;
        }
        
        return num;
        
    }
};