[LeetCode]172.Factorial Trailing Zeroes | 计算阶乘的尾数零的数量

题目来源: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.

思路

  • 计算阶乘数中尾数0个数主要由2和5的数量决定
  • 2的数量远大于5的个数
  • 要求: 5<-->2, 5^2<-->2^2, 5^3<-->2^3, 5^4<-->2^4, 因2^n<5^n,所以主要由5的数量决定
  • 尾数0的个数= sum(n/5^1+n/5^2+n/5^3+…+n/5^m)
    例:5^3<-->2^3,结合后可生成三个0
  • 特殊情况:n=0时, 因不存在0!应返回0

时间复杂度:O(logn), 空间复杂度O(1)

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 172. Factorial Trailing Zeroes
//LeetCode: https://leetcode.com/problems/factorial-trailing-zeroes/
int trailingZeroes(int n) {
int res = 0;
while(n/5 != 0){
n /= 5;
res += n;
}
return res;
}

void main(){
int n = 26;
int res = trailingZeroes(n);
printf("Result trailing zeroes of %d is : %d\n", n, res);
}

运行结果

502 / 502 test cases passed.
Status: Accepted
Runtime: 4 ms
Submitted: 11 minutes ago

总结

  1. 意识到2^n<5^n, 使得5的个数决定了阶乘尾数0的个数
  2. 注意5^n可产生n个0