LeetCode经典算法题之Factorial Trailing Zeroes
LeetCode(172) Factorial Trailing Zeroes
题目描述:
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
即:给定一个数,求其阶乘的结果的尾部0的个数。
分析题目:也就是求一个数的阶乘,然后在返回这个阶乘结果尾部的0的个数,所以我们首先考虑到的应该就是先写一个计算阶乘的方法,算出阶乘后,再将这个数转换成字符串,然后从右到左数出其中0的个数,这个方法应该是大家看到这道题的第一反应(反正菜菜博主的第一反应是这样。但在仔细一想,在数比较小的情况下,这种方法还可行,但一旦数值偏大一点,这种方法的劣势就显现出来了,时间复杂度太高且 n! 的值有可能会超过 2^31 - 1,所以我们要放弃这个方法,重新找一种更好的思路。
再分析:n!末尾有多少个0,我们先举几个例子来看看。
5!=5*4*3*2*1=120
9!=9*8*7*6*5*4*3*2*1=362880
10!=10*9*8*7*6*5*4*3*2*1=3628800
....................
可以看出,0是由2和5相乘得到的,而我们知道数可以分为0、1、质数和合数,而一个数的阶乘就可以表示成若干个质数的乘积,即:
比如5!= 2^1× 3^1×4^1×5^1 等价于 5!= 2^3× 3^1×5^1
10!=2^8× 3^4×5^2
那么这块我们还能发现一个问题,就是在1到n这个范围内,2的次幂x2一定是大于5的次幂x5的,那么题目就更简单了,我们只需要求出n!中5出现的次数,此时的n阶乘为:
现在我们就只需要求出x5,即5出现的次数,
x5 = n/5+n/5/5+n/5/5/5+…… (此处可以用递归来实现,f(n) = n/5+f(n/5))直到商为0,然后求和
代码如下:
大概就是这个样子辣^.^