LeetCode 172. Factorial Trailing

题目

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

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

解析

乍一看，该题是通过求阶乘，然后计算0的数量，但是如果当n是30的时候，所求出的结果已经超出了long long的存储范围。因此采用这种方式提交代码会报Runtime Error。
换一种思考方式，求0的个数，其实就是结果含有多少个10，10 = 2*5，而最终0的个数是由结果中含有5的个数确定的，因此这就显而易见了。

代码

int trailingZeroes(int n) {
    int fiveCount = 0;
    
    while (n != 0) {
        int tmpFiveCount = n / 5;
        
        fiveCount += tmpFiveCount;
        n = tmpFiveCount;
    }
    
    return fiveCount;
}