Factorial Trailing ZeroesGiven an integer

n, return the number of trailing zeroes inn!.

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.