档案日期2014的52

题目描述：

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in ...

题目描述：

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