Problem: Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution: Factorial Trailing Zeroes, Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-02-10 14:08:03
# @Author : NSSimacer
# @Version : 1.0
class Solution:
# @return an integer
def trailingZeroes(self, n):
result = 0
div = 5
while div <= n:
result += n // div
div *= 5
return result

在 OJ 上 AC 过了,时间复杂度 O(log5N) 但是要注意 div 溢出。