Factorial Trailing Zeroes

problem

n!이 주어졌을 때, 뒤에서부터 연속된 0을 찾는 문제입니다.
https://leetcode.com/problems/factorial-trailing-zeroes/

solution

//no: 172
class Solution {
public:
    int trailingZeroes(int n) {
        if(n < 5) return 0;
        return n/5 + trailingZeroes(n/5);
    }
};

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

후기

처음에는 n!을 구하고 시작하려고 했으나, 이 프로그램의 목적이 n!이 아니고 !연산의 경우 숫자가 기하급수적으로 커지므로 문제에 집중하려고 했습니다.

생각해보니까 어떤 두 수를 곱해서 끝자리가 0이라는 뜻은
x = x1 * 10으로 나타낼 수 있다는 뜻이고, 10은 2와 5의 곱으로 만들어지므로,

n!을 보면 2의 경우에는 반복해서 등장하므로 곱해진 5의 갯수만 세면 된다고 생각하게 되어 알고리즘을 만들었습니다.

끝나고 다른 분들의 코드를 보았는데,
n0.2 + n 0.04 ... 이런식으로 /5를 이용하는게 아니라 소수로 곱해버려서 만들어버리는 것을 보고 메모리를 더 적게 쓸 수 있는 방법을 알게 되었습니다.