GuilinDev

Lc0172

05 August 2008

172 Factorial Trailing Zeros

原体概述

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

Example 1:

1
2
3

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

1
2
3

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

题意和分析

题目要求用对数级复杂度O(logn)，如果使用朴素解法就是先求出

1

n!
的值然后取模看最后有多少个0，这个会超出范围；O(logn)的解法：考虑
1

n!
的质数因子，0的得到总是2和5相乘来的，因此需要计算2和5的个数，就解决了， 例如：n=5，(5*4*3*2*1) = (5*2*2*3*2*1)，包含1个5和3个2，因此后缀0的个数是1； 例如：n=11 (…)包含2个5和3个2，因为468可以分解成2，所以质数因子中2的个数总是多于5的个数，因此只要计算5的个数就知道多少个0了； 还有一点要注意的就是25这种，5和5相乘的结果，所以，应该计算n/5里面有多少个5，也就相当于看n里面有多少个25，还有125，625.等等

代码

1
2
3
4
5
6
7
8
9
10

class Solution {
    public int trailingZeroes(int n) {
        int answer = 0;
        while (n > 0) {
            answer += n/5;//这里n/5的个数表示有多少个质数因子5，所以是累加
            n /= 5;
        }
        return answer;
    }
}
This site is open source. Improve this page.