# O(1) and 1 line solution in Java, Python, C

• ``````return n/5 + n/25 + n/125 + n/625 + n/3125;
``````

The number of trailing zeros is equal to how many factors of 10 can be found in 'factorial n'.

The prime factors of 10 is 5 and 2.
Also, in any factorial the number of factors of 2 >= number of factors of 5.
Thus, all I need to do is find the number of factors of 5.

My code does this by finding the number of factors divisible by 5 once (n/5) and adding the number of factors divisible by 5 twice (n/25) and so on.

P.S. this code only works for numbers under 15,625 or 5^6--which is out of range of the problem's input.
This is easily fixed by adding n/15625 and n divided by increasing powers of 5.

• Brilliant!!!

• I don't think this one is O1). for example, can we deem below code as O(1)? because the maximum iteration count is 13, which is a constant

``````int c = 0, d = 5;
for( int i = 0; i < 13; ++i, d *= 5 )
c += n / d;
return c;
``````

if yes, what's the time complexity of below code:

``````int c = 0;
for( ; n > 4; c += (n/=5) );
return c;
``````

if we think this one is O(log(n)), why an O(log(n)) solution always faster (at least not slower) than an O(1) solution?

• I used the same method, but I wrote it in a loop

``````class Solution {
public:
int trailingZeroes(int n) {
int result = 0;
for (__int64 i = 5; i <= n; i *= 5){
result += n / i;
}
return result;
}
};``````

• Could u please explain why should 13 be ok? I tried 14 and 15, not work

• integer overflow, 5^13 < 2^31 < 5^14

• Why do you stop at 3125?!!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.