Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

I used sort of force attempt. TLE… Linear complexity doesn’t fit the requirement. Needs improving.

class Solution {
public:
    int trailingZeroes(int n) {
        if(n < 5) return 0;
        int count = 0;
        long re = 1;
        for(int i = 1; i <= n; i++){
            int ii = i;
            while(ii % 10 == 0){
                ii = ii / 10;
                count++;
            }
            re = re * ii;
            while(re % 10 == 0){
                re = re / 10;
                count++;
            }
        }
        return count;
    }
};

In fact, calculating the trailing numbers of a factorial by multiplying sequential numbers is quite clumsy.

10 is a multiplication of 2 and 5. So… we can do some improvements.