2021-01-18Algorithm3 minutes read (About 417 words) 0 visits

[자바JAVA]172. Factorial Trailing Zeroes

문제 172. Factorial Trailing Zeroes

주어진 int n을 팩토리얼로 나타내어 Trailing Zeroes를 구하는 문제이다.
Given an integer n, return the number of trailing zeroes in n!.

입출력예시

//예시1
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

//예시2
Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

//예시3
Input: n = 0
Output: 0

//예시4
Input: n = 25
Output: 6

코드 및 풀이

팩토리얼 테이블이나 계산기로 확인하여 규칙을 찾을 수 있다.
n이 5의 배수인 경우 규칙을 찾을 수 있다.

팩토리얼	Trailing Zeroes갯수
5!	1
10!	2
15!	3
20!	4
24!	4
25!	6
25!	6
30!	7
50!	12

순차적으로 증가하는 가 싶었지만 25!에서 Trailing Zeroes 갯수는 5가 아니라 6이다.
이를 어떻게 규칙으로 만들 수 있을까?
나눗셈을 한번 더 적용하면 된다.

25/5 = 5 여기서 5를 한번 더 나누면 5/5 = 1이다.
총 5+1로 6을 찾아낼 수 있다.

50!으로해봐도 동일한 결과가 나온다.

즉 규칙은 n이 0보다 클때까지 계속 5로 나누어주는 것이다.
그리고 몫을 누적한 값을 리턴하면 된다.

public class _0172FactorialTrailingZeroes {
  public static int trailingZeroes(int n) {
    int result = 0;
    while( n > 0 ){
      n = n/5;
      result += n;
    }
    return result;
  }

  public static void main(String[] args) {
    int n = //3; //=>0
          // 5;//=>1
          // 0; //=>0
          25; //=>6
    System.out.println(trailingZeroes(n));
  }
}