设计一个算法,计算出n阶乘中尾部零的个数。
样例
11! = 39916800,因此应该返回 2
挑战
O(logN)的时间复杂度。
此问题大致有三种思路:第一种算出结果,然后查看末尾的0的个数,效果非常差;第二种,加法操作,从5开始,每次进5,然后判断,效果达不到O(logN);第三种,每次除5,多次之后结束。
n的阶乘即从1连乘到n的积,尾部0的个数只会由因数2与5的乘积产生,对任意i*2^j都会有小于该数的i*5^j,故因数2的个数>=因素5的个数,所以只需统计因数5^j的个数即可。如果直接计算因数5^2的个数,则算法复杂度较高,那采用什么方法可以降低算法复杂度呢?如下:
对n除5整除,得出因数5的个数;再除5,得出因数25的个数;……;然后累加。
这样i*5^j这个数即会被累加j次,最终1…n中所有5^j次方因数都被累计出来,即可得到最终结果。
/* * 设计一个算法,计算出n阶乘中尾部零的个数 */ #includelong trailingZeros(long n) { // 算法中每次循环均有除以5的操作,也就是每次都会将所要处理的数据量缩小至上一次的1/5,容易推知时间复杂度为O(logN)。 long count = 0; long temp=n/5; while (temp!=0) { count+=temp; temp/=5; } return count; } int main() { int a=5; long result = trailingZeros(a); printf("阶乘 %d 中0的个数: %ld ",a,result); printf("\n"); return 0; }
结果:
阶乘 50 中0的个数: 12