LintCode_尾部的零

本文主要是介绍LintCode_尾部的零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

设计一个算法，计算出n阶乘中尾部零的个数

样例：11! = 39916800，因此应该返回 2

算法实现：

方法一：这是个数学题，最开始就想到应该检测n阶乘中有多少个5的因子，因此采用一个for循环，遍历2~n的每个数，判断能否被5整除，并且能拆分成多少个5的因子，这种方法非常耗时；

    public static long trailingZeros(long n) {<span style="white-space:pre">	</span>//保存n阶乘中尾部零的个数long count=0;//保存0~n中能整整除5的数的个数long count5=0;for(int i=5;i<=n;i=i+5){int j=i;while(j%5==0){count5++;j/=5;}}count=count5;return count;}

方法二：像5,10,15,20等数只有一个5的因子，因此count5++就可以了，但碰到25,50,75等数，包含了2个5的因子，因此count5应该加2，碰到125等含3个5的因子，count5应该加3。因此，可以采用下面的算法。例如105的阶乘，1~105有21个能被5整除的数，105/5=21，1~21中有4个能被5整除的数， 21/5=4，1~4中没有，count5=21+4+0=25.即从1~105中挑出5=5*1,10=5*2，15=5*3,20=5*4,25=5*5,30=5*6...100=5*20,105=5*21这21个数，在从这21个数中挑出能继续被5整除的25,50,75,100这四个数。

（当然，这种算法也是百度出来的）

    public static long trailingZeros(long n) {long count=0;while(n>0){count+=(n/5);n/=5;}return count;}

这篇关于LintCode_尾部的零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---