题目描述:
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in polynomial time complexity.
题目大意:
给定一个整数n,返回n!(n的阶乘)数字中的后缀0的个数。
注意:你的解法应该满足多项式时间复杂度。
解题思路:
参考博文:http://www.geeksforgeeks.org/count-trailing-zeroes-factorial-number/
朴素解法:
首先求出n!,然后计算末尾0的个数。(重复÷10,直到余数非0)
该解法在输入的数字稍大时就会导致阶乘得数溢出,不足取。
O(logn)解法:
一个更聪明的解法是:考虑n!的质数因子。后缀0总是由质因子2和质因子5相乘得来的。如果我们可以计数2和5的个数,问题就解决了。考虑下面的例子:
n = 5: 5!的质因子中 (2 * 2 * 2 ...