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