Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
结果转换成3进制，结尾有多少个连续的0？
在面试时，曾遇到这样的一道题：
30!结果转换成3进制，结尾有多少个连续的0？
第一次做的话，感觉没有思路，但是换个角度想，转换成3进制，那么十进制中的1~30，哪些因子相乘，才会贡献出三进制结尾的0呢？当然是：3的倍数。
3， 6， 9， 12， 15 ，18， 21， 24， 27， 30
那么，每一个因子贡献了多少个0呢？
贡献了1个0的因子
代码语言：javascript复制3 = 3 * 1
6 = 3 * 2
12 = 3 * 4
15 = 3 * 5
21 = 3 * 7
24 = 3 * 8
30 = 3 * 1030/3 30/9 30/27所代表的，就是最终结果。
这是因为：30/3把所有贡献了0的因子都算了一次，9、18、27已经被算过一次了，但是9和18还有一个因子没有算，27中还有两个因子没有算。
30/9则计算了一次9、18、27，但是27中还有一个因子没有算。
30/27计算了一次27，至此，所有的因子都计算完毕。
在代码中，一定要注意溢出的问题，如下代码（我的第一个代码）就不能通过测试。因为在n很大时，比如Integer.MAX_VALUE，i *= 5溢出了，i一直是小于等于n，所以是死循环！
代码语言：javascript复制 public static int trailingZeroes2(int n) {
int rt = 0;
for (int i = 5; i <= n; i *= 5) {
rt = n / i;
}
return rt;
}解决方法，把n定义成long型。注意i也要定义成long型，否则在n很大时，主要是i * 5 > Integer.MAX_VALUE后会出错。
代码语言：javascript复制 public int trailingZeroes(int n) {
int rt = 0;
long N = n;
for (long i = 5; i <= N; i *= 5) {
rt = N / i;
}
return rt;
}
