设计一个算法,计算出n阶乘中尾部零的个数
样例
11! = 39916800,因此应该返回 2
对于这个问题,我们的思路如下,首先要想得到尾部为0,那么一定是乘以5或者5的倍数,才会得到这样的结果,那么举一个例子,我们设参数为101,也就是101的阶乘尾部有多少个零,我们列举一下5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100,这些数和偶数相乘都可以得到尾部为0的数,(这里的偶数数量够不够这个问题我们完全不用考虑,因为阶乘可以为我们提供足够的偶数)那么这样的数到底有多少?用101/5(整除)=20,我们知道有20个,但是,有没有发现一个问题,25,50,75,100这些数和足够偶数相乘都是尾部会有两个0的,那么我们发现10/5=20,20的用处在哪里?
让我们再想象一下,假如是求1001的阶乘,1001/5=200,此处求出来的是从1到1001之间(包括1和1001)是5的倍数的数有多少个,那么我们要求25(5*5)的倍数呢,125(5*5*5)的倍数呢?
回到101的阶乘这个问题上,101/5=20;101/5/5=20/5=4,可以知道有4个数是25的倍数,25的倍数也肯定是5的倍数,在计算尾部0个数的时候,只需要加上是25的倍数的个数即可。
代码很简单,使用递推(不是递归!!!谢谢指正~)即可,如下:
public class Solution { /* * @param n: An integer * @return: An integer, denote the number of trailing zeros in n! */ public long trailingZeros(long n) { // write your code here, try to do it without arithmetic operators. long sum=0; while(n/5!=0){ n=n/5; sum+=n; } return sum; } }