[LeetCode] 172. Factorial Trailing Zeroes

Problem

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 <= 10^4

---

Solution

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (0 < n) {
            n /= 5;
            count += n;
        }
        return count;
    }
}

Explanation

• 정수n의 증가에 따른 팩토리얼을 나타내면 다음과 같다.

n	n!	Trailing zeroes
1	1	0
2	2	0
3	6	0
4	24	0
5	120	1
6	720	1
7	5,040	1
8	40,320	1
9	362,880	1
10	3,628,800	2
11	39,916,800	2
12	479,001,600	2
13	6,227,020,800	2
14	87,178,291,200	2
15	1,307,674,368,000	3
16	20,922,789,888,000	3
17	355,687,428,096,000	3
18	6,402,373,705,728,000	3
19	121,645,100,408,832,000	3
20	2,432,902,008,176,640,000	4
21	51,090,942,171,709,440,000	4
22	1,124,000,727,777,607,680,000	4
23	25,852,016,738,884,976,640,000	4
24	620,448,401,733,239,439,360,000	4
25	15,511,210,043,330,985,984,000,000	6
	…
30	265,252,859,812,191,058,636,308,480,000,000	7

• 어떤 짝수에 5를 곱하게 되면 Trailing zero가 하나 생긴다. 그리고 10을 곱하게 되면 2를 곱하고 5를 곱하는 꼴이 되므로 또한 Trailing zero가 하나 생긴다. 또한 25를 곱하게 되면 5를 곱하고 5를 곱하는 것과 같기 때문에 Trailing zero가 두개 생기게 된다.
• (n - 1)!의 값에서 Trailing zeroes를 제외한 부분은 n이 1일 때를 제외하고는 항상 짝수이기 때문에 n이 5의 배수이면 Trailing zero가 증가하게 된다.
• 따라서 n!에 곱해진 5의 개수를 구하면 Trailing zeroes를 알아낼 수 있다.
• 반환을 위한 변수 count를 선언한다.

  int count = 0;
  

• n을 5로 나누면 0 ~ n사이에 존재하는 5의 배수의 개수를 알 수 있다.

  n /= 5;
  count += n;
  

• 여기서 한 번 더 5로 나눌 수 있다는 것은 25와 같은 5의 제곱인 수가 0 ~ n사이에 존재한다는 의미가 된다. 5의 배수의 개수에 5의 제곱인 수를 더해주어야 Trailing zeroes의 개수를 구할 수 있기 때문에, n을 5로 나눌 수 없을 때까지 나누기 위해 while 반복문을 작성한다.

  while (0 < n) {
    n /= 5;
    count += n;
  }
  

• Trailing zeroes의 개수를 의미하는 변수 count를 반환한다.

  return count;