CODEWITHSUNDEEP
pythonpython-2.7optimization
Atharva Chandra
Atharva Chandra

Reputation: 37

Time limit exceeded on spoj.FCTRL

I have to generate the number of trailing zeros at the end of factorial of a integer.first input is the no of test cases'T'. Next T lines contain the input integers. Output should have the number of zeros at the end of factorial of input integers. Here is my code but it gives time limit exceeded.Please help me optimize .

T=int(raw_input())
a=[]
for i in range(0,T):

    a.append(int(raw_input()))
def factorial (n):
    fact=1
    while(n>0):
        fact=fact*n
        n=n-1
    return fact

b=[]
for i in range(0,T):
    b.append(factorial(a[i]))


c=[]

for i in range(0,T):
    ans=0
    while(b[i]%10 == 0):
        ans=ans+1
        b[i]=b[i]/10
    c.append(ans)
for i in range(T):
    print c[i],

Upvotes: 1

Views: 173

Answers (1)

Ashot
Ashot

Reputation: 10979

Since the input numbres are quite big you can't calculate factorials of them. It takes too long. Think about algorithm that counts numbers of trailing 0s without calculating factorials. In fact each trailing 0 appears after multiplying 5 by some even numbres. So you need to calucate number of 5 factors in all numbres lower the input.

For example 27! ends by 6 zeros because in the range (1, 27) 5 factor has only these numbres

5(1) 10(1) 15(1) 20(1) 25(2). 25 has two factors of 5.

Upvotes: 2

Related Questions