[LeetCode Road] Factorial Trailing Zeroes - Solution/C++

172. Factorial Trailing Zeroes

Question:

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:

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

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

Input: n = 0
Output: 0

Source code:

Version 1

Idea:
I give some examples of different n:
if n = 5, 5! = 120
if n = 9, 9! = 362880
if n = 10, 10! = 3628800
if n = 15, 15! = 1307674368000
if n = 20, 20! = 2432902008176640000
if n = 25, 25! = 15511210043330985984000000

Above the examples, we can get some rules:

1. tailling zeros means factor of 10 in the factorial
2. finding tailling zeros means counting the number of factor of 5 for the factorial of n
3. dividing n to get the additional number of factor of 5s

Notice: At n = 25 case, 5 times 5 is 25 (two of 5s),so it has 5 + 1 of 5s.
Finally, we need to divide n to count the number of additional factors of 5.

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