Leetcode 172) Factorial Trailing Zeros

13 Apr 2021 in Algorithms

Wrong : 25, 75같은 수는 5로 여러번 나눠떨어지는데, 그냥 5를 한번만 count 해서..

class Solution {
    public int trailingZeroes(int n) {
        int a=n;
        int five=0;
        while (a>0){
            if(a%5==0){
                five++;
            }
            a--;
        }
        return five;
    }
}

Right, but not that good performance.

class Solution {
    public int trailingZeroes(int n) {
        int a=n;
        int five=0;
        while (a>0){
            int fiveDetector=a;
            while(fiveDetector%5==0){
                five++;
                fiveDetector = fiveDetector/5;
            }
            a--;
        }
        return five;
    }
}

아 이렇게 하면 더 간단하게 되는구나
102 까지 수 중, 5로 나누어 떨어지는 수가 20개가 있다. –> 2번이랑 겹치지 않나..?아!! 2번이랑 겹쳐도 되는구나!!! 왜냐면 2번에서 두번카운트 되는 대신, 여기서 한번 카운트, 2번에서 한번 카운트 총 두번 이렇게 들어가니까!!
102 까지 수 중, 25로 나누어 떨어지는 수가 4개 있다.
102까지 수 중, 125로 나누어 떨어지는 수가 0개 있다.

이런식으로!

class Solution {
    public int trailingZeroes(int n) {
        int grad = 5;
        int ans = 0;
        while (n >= grad){
            ans += n / grad;
            grad *= 5;
        }
        return ans;
    }
}