归档 2014年12月30日

[LeetCode]Factorial Trailing Zeroes

题目描述:

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 ...

继续阅读

昨天

明天

归档