[알고리즘/자바스크립트] 꼬리에 붙은 0 (팩토리얼과 Trailing Zero)

[문제] 주어진 숫자의 팩토리얼을 계산한 값에서, 마지막에 연속되어 붙어있는 0이 몇개인지 반환해주는 함수를 완성해주세요! (팩토리얼을 계산하지 않고 구하기!)

 

참고로, N 팩토리얼이란 다음과 같은 것을 말합니다.

(factorial은 !로 표기합니다. 더 많은 내용은 http://mathworld.wolfram.com/Factorial.html를 참고해주세요)

N! = 1 * 2 * 3 * ... * N

 

예를들어,

trailingZeros(6) = 1

왜냐하면, 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720 --> 1 , 끝에 1개의 0이 있습니다.

 

trailingZeros(12) = 2

12! = 479001600 --> 2, 꼬리에 2개의 0이 있습니다.

 

@param {number} n

@return {number}

 

---

 

 

일단 이 문제를 풀기 위해 나는 1부터 10까지 팩토리얼을 구해보았다.

 

1! = 1

2! = 1 * 2 = 2

3! = 1 * 2 * 3 = 6

4! = 24

5! = 120

6! = 720

7! = 5,040

8! = 40,320

9! = 362,880

10! = 3,628,800

 

여기서 0이 생기는 시점의 숫자를 잘 보면 5의 배수라는 점을 알 수 있다.

 

위 논리대로 1부터 100까지 수 중에서 5의 배수인 수로 팩토리얼을 구한 후,

마지막 0의 개수, 즉 trailing zero를 표로 만들어보았다.

 

factorial	trailing zero	factorial	trailing zero	factorial	trailing zero	factorial	trailing zero
5!	1개 (+1)	30!	7개 (+1)	55!	13개 (+1)	80!	19개 (+1)
10!	2개 (+1)	35!	8개 (+1)	60!	14개 (+1)	85!	20개 (+1)
15!	3개 (+1)	40!	9개 (+1)	65!	15개 (+1)	90!	21개 (+1)
20!	4개 (+1)	45!	10개 (+1)	70!	16개 (+1)	95!	22개 (+1)
25!	6개 (+2)	50!	12개 (+2)	75!	18개 (+2)	100!	24개 (+2)

 

신기한 규칙을 발견할 수 있는데, 즉 5의 배수가 될 때마다 trailing zero의 개수가 1개씩 증가하고

25의 배수가 될 때마다 trailing zero의 개수가 2개씩 증가한다는 점이다.

이 때까지만 해도 감이 안왔는데 계속해서 숫자를 구해보니

125의 배수가 되었을 때 trailing zero의 개수가 3개씩 증가하였다.

 

 

5	5	5^1	0이 1개씩 증가
25	5 * 5	5^2	0이 2개씩 증가
125	5 * 5 * 5	5^3	0이 3개씩 증가

 

 

그렇다면 이 규칙대로라면 100!의 trailing zero 개수는 (100 / 5)의 정수몫 + (100 / 25)의 정수몫이 될 것이다.

만약 128!의 trailing zero 개수를 구한다면 (128 / 5)의 정수몫 + (128 / 25)의 정수몫 + (128/ 125)의 정수몫이 될 것이다.

 

 

즉, A라는 수가 있으면 A를 [A보다 작지만 A에 가장 근접한 5의 배수]로 나눈 값을 반복해서 더해주면 된다.

 

 

 

function trailingZeros (n) {
  var countZero = 0;
  var p = 1;
  while (n > 5**p) {
    countZero += Math.floor(n / 5**p);
    p++;
  }
  return countZero;
}

첫 번째 풀이이다. while문을 사용했고,

[5**1 => 5의 1승], [5**2 => 5의 2승]인 것을 이용하여 풀었다.

 

function trailingZeros (n) {
  var countZero = 0;
  var p = 1;
  while (n > p) {
    p *= 5;
    countZero += Math.floor(n / p);
  }
  return countZero;
}

역시나 while문을 사용했다.

다른 점은 p에 5를 계속 곱하여 사용하는데,

위의 코드보다 훨씬 간결하고 알아보기 쉬운 코드인 것 같다.

 

function trailingZeros (n) {
  var countZero = 0;
  for (var p = 5; p < n; p *= 5) {
    count += parseInt(n / p);
  }
  return countZero;
}

똑같은 방법인데 for문을 사용하여 풀었다.

 

 

 

---

 

위 팩토리얼과 trailing zero의 규칙에 대해서 좀 더 수학적으로 이해하고 싶어서

인터넷을 찾아보다가 아래의 게시글을 읽어보고 큰 도움을 받았다.

 

https://brilliant.org/wiki/trailing-number-of-zeros/

Trailing Number of Zeros | Brilliant Math & Science Wiki