[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