172. Factorial Trailing Zeroes

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

Follow up: Could you write a solution that works in logarithmic time complexity?

Example 1:

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

Example 2:

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

Example 3:

Input: n = 0
Output: 0

解法一

class Solution {
public:
    int trailingZeroes(int n) {
        
        int res=0;
        for(int i=5;i<=n;i=i*5){
            res+=n/i;
        }
        return res;
    }
};

10是2*5，因為2一定很多個，因此計算5的個數即可知道有幾個尾巴的0。

但要注意的是25、125...會有重複的5沒被計算到，因此跳一步為i = i*5

解法二

class Solution {
public:
    int trailingZeroes(int n) {
         return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
      
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Factorial Trailing Zeroes.

Memory Usage: 5.8 MB, less than 70.29% of C++ online submissions for Factorial Trailing Zeroes.