[문제]

Write a program that will calculate the number of trailing zeros in a factorial of a given number.

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

Be careful 1000! has 2568 digits...

For more info, see: http://mathworld.wolfram.com/Factorial.html

Examples

zeros(6) = 1
6! = 1 2 3 4 5 * 6 = 720 --> 1 trailing zero

zeros(12) = 2
12! = 479001600 --> 2 trailing zeros

Hint: You're not meant to calculate the factorial. Find another way to find the number of zeros.

(요약) 주어진 숫자 n에 대해 n!의 값을 구할 때 일의 자리부터 0이 몇 번 연속으로 나오는지 구해라

[풀이]

우선 내가 하려고 했던 방법은

숫자를 곱할 때 낮은 자리에 0이 나오려면 무조건 5와 2의 곱이 되어서 10을 만들어야 한다.

factorial은 1부터 하나씩 증가시켜서 모든 숫자를 누적해서 곱하는 것이므로 5가 한 번 나올 때 짝수는 2개는 포함하고 있으니 5만 몇 번 들어가는지만 구하면 된다.

1.

function zeros (n) {
  let answer = 0;

  for(let i = 5; i <= n; i += 5) {
    let num = i;

    while(!(num % 5)) {
      answer++;
      num /= 5;
    }
  }

  return answer;
}

처음 했던 방식은 반복문을 두 번 이용해서 5의 배수가 5를 몇개 가지고 있는지 였는데 n이 크면 타임아웃이 나버려서 다른 방법을 생각

2.

function zeros (n) {
  let answer = 0;
  let currentNum = 5;
  let dividedNum = currentNum;

  while(currentNum <= n) {
    if(!(dividedNum % 5)) {
      dividedNum /= 5;
      answer++;
    }
    else {
      currentNum += 5;
      dividedNum = currentNum
    }
  }

  return answer;
}

처음 했던 방식이랑 원리는 같은데 2중 반복문이 아니라 반복문을 하나만 사용했는데도 타임아웃이 남.

3.

function zeros (n) {
  let answer = 0;
  let divideNum = 5;

  while(divideNum <= n) {
    answer += (n / divideNum)|0;

    divideNum *= 5;
  }

  return answer;
}

5가 몇개 들어가는지 어떻게 찾아야 될까 계속 생각하다가 그 수를 5로 나눈 몫이 결국 5를 포함하고 있는 개수란걸 이용하기로 함.

우선 n을 5로 나눠서 몫을 구한다.

5가 거듭제곱으로 구성되어 있는 경우도 같은 방식으로 계산하면 된다.

먼저 5로 나눈 몫을 구하고, 그 다음 25로 나눈 몫을 구하고, 125로 나눈 몫을 구하고...

n보다 작은 5의 거듭제곱으로 나누는 경우만 생각해서 구하면 끝.