Number of trailing zeros of N!, CodeWars Kata 자바 솔루션

 

Number of trailing zeros of N!, CodeWars Kata

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.

팩토리얼 연산의 결과값의 하위 자리에 0이 몇개가 포함되어 있는지를 계산하는 문제입니다. 팩토리얼을 구현한 후 0의 개수를 세리지 말고 다른 방법으로 찾아보라고 힌트가 주어지네요.

 

My Solution

먼저 팩토리얼 연산을 했을 때 0이 몇 개가 포함되어 있는지 예시를 통해서 파악을 해보았습니다. 코드 아래쪽에 주석으로 쓴 것들이 전부 0이 어떻게 증가하는지 파악하기 위해서 찾은 예시들입니다.

아래 주석에는 나와있지 않지만 1부터 4까지는 0이 하나도 붙지 않고, 5부터 붙습니다. 그리고 10이되면 0이 하나 더 늘어나고요. 15가 되면 0이 하나 더 늘어납니다. 5의 배수마다 0이 하나씩 늘어나는 것을 알 수 있습니다.

조금 더 살펴 보면 25팩토리얼은 그 전과 다르게 0이 하나 더 붙습니다. 50팩토리얼은 0이 두 개 더 붙고요. 100 팩토리얼도 0이 두 개 더 붙습니다. 25의 배수는 아니라는 결론입니다.

더 찾아보면 125가 되면 0이 세 개가 더 붙는 것을 알 수 있습니다. 그래서 625를 찾아보니 0이 네 개가 더 붙네요. 5와 5의 제곱수들로 나눈 몫의 합만큼 0이 늘어난다는 결론이 납니다.

그래서 저는 재귀 함수를 이용해서 연산이 거듭될 때마다 5의 제곱, 세제곱들로 나눌 수 있도록 해서 그 몫의 합을 구했습니다.

 

솔루션 코드

테스트 코드

package com.codewars;

public class NumberOfTrailingZerosOfN {
    public static int zeros(int n) {
        int div = getDiv5(n, 5, 0);
        return n == 0 ? 0 : div;
    }

    public static int getDiv5(int num, int div, int count) {
        int last = num / div;
        if (last >= 0 & div <= num) {
            count = getDiv5(num, div * 5, count + last);
        }
        return count;
    }
}


// 20 4
// 25 6 // 5 + 1
// 30 7 6 + 1
// 35 8
// 40 9
// 45 10
// 50 00 00000 00000 12
// 51 00 00000 00000 12
// 55 000 00000 00000 13
// 60 0000 00000 00000 14
// 65 00000 00000 00000 15
// 70 0 00000 00000 00000 16
// 75 000 00000 00000 00000 18
// 99 00 00000 00000 00000 00000 22 19 +
// 100 0000 00000 00000 00000 00000 24
// 124 0000000000000000000000000000 28
// 125 0 00000 00000 00000 00000 00000 00000 31 3
// 149 00000 00000 00000 00000 00000 00000 00000 35
// 150 00 00000 00000 00000 00000 00000 00000 00000 37
// 249 59
// 250 62
// 499 121
// 500 125
// 624 152
// 625 156 4
// 999 246
// 1000 249 4
// 199 + 39 + 7 + (245) + 1
// 100 + 20 + 20/5 = 4 + 1
// 200 + 40 + 40 /5 + 1
// 15625

 

Best Practice

BP1

이 BP가 가장 효율적인 방법인 것 같습니다. 우리는 5의 제곱수들로 나눈 몫의 합이 필요한데 이것은 for의 증감값으로 해결이 가능합니다. 재귀 함수는 코드양을 줄여주는 효과가 있지만 연산이 길어지면 스택을 많이 사용한다는 단점이 있습니다. 가능하면 반복문을 쓰는 것이 더 좋겠지요.

package com.codewars;

public class NumberOfTrailingZerosOfN {
    public static int zeros(int n) {
        int res = 0;
        for (int i = 5; i <= n; i *= 5) {
            res += n / i;
        }
        return res;
    }
}

 

BP2

두번째는 재귀 함수를 이용한 연산입니다. 제가 작성한 코드보다 훨씬 깔끔하고 별도의 메소드 작성도 하지 않았습니다. 저는 5의 제곱수로 나누었지만 아래 재귀 함수는 재귀할 때마다 입력값을 5로 나눈 수를 입력값으로 가집니다. 메모리를 조금 더 효율적으로 사용할 수 있겠죠.

package com.codewars;

public class NumberOfTrailingZerosOfN {
    public static int zeros(int n) {
        if (n / 5 == 0)
            return 0;
        return n / 5 + zeros(n / 5);
    }
}