TLE for trailing zeros


#1

I am getting TLE for following python code:

class Solution:
    # @param A : integer
    # @return an integer
    def factorial(self,n):
        fact = 1
        while n > 1:
            fact *= n
            n -= 1
        return fact
    def trailingZeroes(self, A):
        fact = self.factorial(A)
        counter = 0
        while True:
            if fact % 10 == 0:
                counter += 1
                fact //= 10
            else:
                break
        return counter

for the input 9980. In my local machine it runs in 01.122321 time. Is that too slow for interviewbit?


#2

Calculating factorial is the bottleneck in your code. You can do this problem without factorial. Trailing zeros depend on the no.of 10’s that will be in your factorial.
Example 5! = 5 * 4 * 3 * 2 * 1 = 12 * 10 = 120 => 1 ten, so 1 zero