FactorialTrailingZeroes [source code]

public class FactorialTrailingZeroes {
static
/******************************************************************************/
public class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        for (int i = 1; i <= 13; i++) {
            count += n / Math.pow(5, i);
        }
        return count;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FactorialTrailingZeroes.Solution tester = new FactorialTrailingZeroes.Solution();
    }
}

这一题直接把阶乘乘出来再做肯定是不行的, 首先复杂度不够快, 其次肯定会overflow;

这个问题在 xiao8的水友群里面好像还碰到人讨论过;

思考了一下, 大概还是把这个算法做出来了, 代码本身就没什么好讨论的, 主要是背后的数学原理. 最后的速度是2ms (5%), 这个有点意外, 不过可能是因为题目有点老了(172), 所以大部分人都知道正确答案了;

这个是 submission 最优解:

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

我使用的是5的 pow 来做, 他这个做法更聪明, 直接每数一次5, 就把数过的5直接消除掉;

discussion里面认为, 可以稍微修改一下, 最后只有一个1liner 就可以了:

return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);

这个也很聪明;
他们这个代码还有一个好处就是非常好的解释了为什么最后的复杂度是 logN, 因为他们这里有明确的"除5"的操作; 我这个因为混杂了 pow 的操作, 所以解释起来还可能麻烦一些;

这个是上面的 recursion 改成了 tail recursion:

int trailingZeroes(int n, int ret = 0) {  
        return n == 0 ? ret : trailingZeroes(n / 5, ret + n / 5);  
}

Problem Description

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

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:93.4K
Total Submissions:261.2K
Contributor: LeetCode
Companies
bloomberg
Related Topics
math
Similar Questions
Number of Digit One