LeetCode-172-阶乘后的零

Posted on | In | Views:

LeetCode-172-阶乘后的零

1. 题目：

阶乘后的零

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

1
2
3
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

1
2
3
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

2. 解题：

我们需要找到阶乘末尾有多少个0，直接求出阶乘的结果，再数0的个数是无法实现的，因为当n比较大时，阶乘后的结果会溢出。

核心就是，乘法中出现0的情况。

1
2
3
4
5
6
7
3! = 6	没有0
5! = 5*4*3*2*1 = 120 有1个0，并且是因为2*5才会得到0
10! : 2*4*6*8*5*10 = 2*5*(2*5)*4*6*8 -> 2个0
因此，找0就成了找2,5以及其倍数，2的个数要多于5，因此就是来找5的个数。
但是还要考虑：
31! : 5*(2*5)*(3*5)*(4*5)*(5*5)*(6*5) ->有7个5 ->有7个0
所以我们需要找(5^n)的个数，比如5,25,125...

代码：

1
2
3
4
5
6
7
8
9
class Solution {
    public int trailingZeroes(int n) {
        int countZero = 0;
        while(n > 0) {
            countZero += (n /= 5);
        }
        return countZero;
    }
}