Although my program runs within a time limit 8 sec, yet I receive a time Limit error.

The problem and solution are:

https://www.codechef.com/viewsolution/14556827

Although my program runs within a time limit 8 sec, yet I receive a time Limit error.

The problem and solution are:

https://www.codechef.com/viewsolution/14556827

Hey to find exponent of prime p in n! we have a formula Ep(n!) = [n/p] + [n/p²]+…+[n/ps].

If you have any doubt see this

But, why does my program gives a time limit error?

while(T!=0)

{

long int n;

cin>>n;

for(int i=1;i<=n;i++)//THIS is causing TLE.

N can be upto 10^9, while online judge can perform only K x 10^8 instructions a second. You will easily exhaust you time for larger input, especially when T is `(equal to about 100000)`

. In worst case, if i enter numbers ~10^9 T times, you are consuming ~10^14 instructions, which will give you a TLE.

Try to remove that for loop, its possible to do it in logarithmic time.

1 Like