Factorial Trailing Zeroes

Problem

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

Note: Your solution should be in logarithmic time complexity.

Solution

O(n) Solution

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

Analysis

The only way to have zeroes in our factorial result is 2 * 5 = 10
Therefore, we just need to calculate how many 5 and 2 in the factorial expression
However, as long as we have 5 there must be 2 because there must be an even number among five numbers
Hence, we just need to calculate how many 5 we have in multiplier