描述
设计一个算法，计算出n阶乘中尾部零的个数
样例
样例 1:
输入: 11
输出: 2
样例解释:
11! = 39916800, 结尾的0有2个。
样例 2:
输入: 5
输出: 1
样例解释:
5! = 120， 结尾的0有1个。
挑战
O(logN)的时间复杂度
算法思路
首先,我们需要知道N的阶乘是如何运算的
N! 代表N的阶乘
N! = 1 * 2 * 3 * 4 * 5 * 6 * 7 ... * N-1 * N
简而言之,就是从1乘到N
然后,我们需要知道尾部的0是如何出现的
经过观察,我们发现尾部的0是 5和偶数相乘 得到的
所以该问题转换为从1乘到N,里面有多少个5相乘
从1开始,那么每数5个数一定是5的倍数,即最少含有一个5进行最后的乘法运算
所以我们首先以5作为步长,可查出有多少个符合条件的数 即 a = N/5
我们定义sum = 0 为N的阶乘尾部的0的结果
我们将算得的数字加起来 sum += a
它们类似:
5 10 15 20 25 30 35 40 45 50 55 60...
但其中有些5的倍数中,还存在多个5相乘,比如25是5 * 5,125是5 * 5 * 5,也需要计算出来
根据规律,每5个又会多出现一个5,所以再除以5 a = a/5
我们将算得的数字加起来 sum += a
它们类似:
25 50 75 100 125 150 175 200 225 ...
此时我们已经计算出两个5,但数据中还可能出现包含更多5的数字,如125包含3个5相乘,也需要计算出来
根据规律,每5个又会多出现一个5相乘,所以再除以5 a = a/5
我们将算得的数字加起来 sum += a
以此类推,直至除得的结果除不开五,sum即为所求0的数量
代码
public static long getZero(long num) {
long sum = 0;
while (num != 0) {
num /= 5;
sum += num;
}
return sum;
}
