NC129 阶乘末尾0的数量

描述
给定一个非负整数 n ，返回 n! 结果的末尾为 0 的数量。

n! 是指自然数 n! 的阶乘,即 : N!=1×2×3…(N−2)×(N−1)×N。
特殊的, 0 的阶乘是 1 。

数据范围：0

进阶：空间复杂度 O(1)，时间复杂度 O(logn)
复杂度要求：
不大于 O(logn)

示例1
输入：3
返回值：0
说明：
3!=6     

示例2
输入：5
返回值：1
说明：
5!=120    

示例3
输入：1000000000
返回值：249999998
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

思路：10以内的乘法会产生0的只有：
25 = 10；45=20；65=30；58=40.
其中4，6，8都为2的倍数
因此，阶乘中看有多少2*5即可得到有多少0
而5的因子一定比2的因子少，因为5相对大一点。则看阶乘中多少个5
其中，5的倍数至少能产生1个5，25的倍数至少能产生2个5
故：

其中，5的倍数为5个，25的倍数为1个

import java.util.*;


public class Solution {
    /**
     * the number of 0
     * @param n long长整型 the number
     * @return long长整型
     */
    public long thenumberof0 (long n) {
        // write code here
        if(n<=0 || n>Math.pow(10,14)) return 0;
        long ans = 0;
        long d = 5;
        while(n >=d){
            ans += n/d;
            d = d*5;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21