[C] LeetCode 172. Factorial Trailing Zeroes

문제(영어)

문제(번역)

정수 n이 주어질때, n!에서 오른쪽 끝에 있는 0의 개수를 구해라.

n! = n * (n-1) * ... * 2 * 1 인 것을 기억해라.

 

접근 방법  

팩토리얼 결과의 맨 뒤에 0은 언제언제 붙을까? 

0은 10이 곱해질때마다 생길 것이다. 그럼 10은 2와 5의 곱으로 생긴다.

우리는 여기에서 5에 집중을 해야 한다.

2는 생각보다 자주 나오지만, 5는 자주 나오지 않는다.

즉 뒤에 붙는 0의 수는 5가 나오는 수와 동일하다고 간주하면 된다!

그럼 답이 정말로 간단해진다.

 

소스코드

int trailingZeroes(int n) {
    int c = 0;
    while(n > 0) {
        c += ( n/=5 );
    }
    return c;
}

 

공간복잡도도 O(1)이고, 해당 코드는 반복문이 최대 log_5 (n)번 돌아가기 때문에 O(log n) 의 시간복잡도를 갖게 된다.