172. Factorial Trailing Zeroes

1. Description

Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1.

2. Example

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

3. Constraints

• 0 <= n <= ${10}^4$

4. Follow up

• Could you write a solution that works in logarithmic time complexity?

5. Solutions

Math

Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5; 
            count += n;
            // n / 5 is the number of 5 
            // but 25, i.e., 5 * 5 has two 5, n / 5 will only count it once
        }

        return count;
    }
};