172. Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

这道题最好用数学解法,如果末尾为0,那么必然2*5,所以只要数对数即可。但是依旧超出了时间(要一个个对于大数来说,还是太多)。以下是网上找到的最佳办法解释

这道题并没有什么难度,是让求一个数的阶乘末尾0的个数,也就是要找乘数中10的个数,而10可分解为2和5,而我们可知2的数量又远大于5的数量,那么此题即便为找出5的个数。仍需注意的一点就是,像25,125,这样的不只含有一个5的数字需要考虑进去。

class Solution {
    public int trailingZeroes(int n) {
        if(n == 0) return 0;
        // int two = 0;
        // int five = 0;
        // while(n > 1){
        //     int tmp = n;
        //     while(tmp%2 == 0){
        //         two ++;
        //         tmp = tmp/2;
        //     }
        //     while(tmp%5 == 0){
        //         five ++;
        //         tmp = tmp/5;
        //     }
        //     n--;
        // }
        // return Math.min(two,five);
        
        int sum = 0;
        while(n>4){
            sum += n/5;
            n = n/5;
        }
        return sum;
        
        
    }
}

喜欢的话订阅一个呗~第一时间收到文章更新哟~

发表评论

电子邮件地址不会被公开。