CODEWITHSUNDEEP
pythoncalgorithm
user3154219
user3154219

Reputation: 83

SPOJ same algorithm accepted in C, Time limit Exceeded in Python

I am trying to solve the FCTRL problem from SPOJ. The problem is to find the number of trailing zeroes in N! for some T test cases.

T ~ 1,00,000.
1 <= N <= 1000000000

My problem is very strange. If I try the following C code, it gets accepted with time 0.22 seconds and a memory usage of 1.6M. But if I submit the equivalent Python 3 code, it says Time Limit Exceeded with memory usage of 11M.

C Code:

#include <stdio.h>

void fact_zeros(long int);

int main(void) {
    long int i,t,n;
    if (scanf("%ld",&t) > 0) {
        for (i=1;i<=t;i++) {
            if (scanf("%ld",&n) > 0) {
                fact_zeros(n);
            }
        }
    }
    return 0;
}

void fact_zeros(long int N) {
    long int zeros = 0;
    while (N>0) {
        N = N / 5;
        zeros += N;
    }
    printf("%ld\n",zeros);
}

Python 3 Code:

"""
spoj11Factorial.py
This program calculates the number of zeroes at the 
end of the factorial of each number of the test case.
"""

def fact_zeroes( n ):
    count_5s = 0
    while (n > 0):
        n = n // 5
        count_5s += n
    return count_5s


T = int( input() )
while (T):
  T -= 1
  n = int( input() )
  zeroes = fact_zeroes( n )
  print( zeroes )

Can anyone please spot what different / wrong I am doing in the Python code. It works for all given test cases on my machine.

Thanks.

EDIT: Problem Specifications:

Added by:   Adrian Kosowski
Date:   2004-05-09
Time limit: 6s
Source limit:   50000B
Memory limit:   256MB
Cluster:    Pyramid (Intel Pentium III 733 MHz)
Languages:  All except: NODEJS PERL 6
Resource:   ACM Central European Programming Contest, Prague 2000

Upvotes: 4

Views: 1068

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

One very easy way to more than double the speed of this program is to convert:

n = int( input() )

to

n = int( raw_input() )

Note that raw_input() returns a string from the input, while input() runs the Python interpreter on the string after reading it.

On my computer using Python 2.7 this reduces the time from 1.6 seconds to 0.7 seconds

Upvotes: 6

Related Questions