导航
导航
文章目录
  1. 题目
  2. 翻译

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.

翻译

给出一个整数n,返回n!末尾有几个0。
注意: 你的解时间复杂度应控制在O(logn)。

开始考虑当遇到2、5、10的时候会出现末尾的0,但忽略了像25这种,会产生两个0的数字。
因此分别算出n中包含几个5、几个25、几个125……即可,然后加和:

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int trailingZeroes(int n) {
int trailingZeroes = 0;
while (n > 0) {
trailingZeroes += n / 5;
n /= 5;
}

return trailingZeroes;
}
}

参考:
http://blog.csdn.net/doc_sgl/article/details/42344441