Why am I getting TLE?

nukes
tle

#1

Can anyone tell me why I am getting TLE in
http://www.codechef.com/viewsolution/4855478
?


#2
  • In your code, ‘b’ represents ‘A’ as
    mentioned in the problem. A < 10^9.

  • And your solution has the loop
    while(k–){}. Hence your solution
    will take approximately A steps, or
    in easier way, the number of steps of
    your problem is of the order A. Hence
    your code is an O(A) solution. For
    algorithm analysis:
    http://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/

  • Now, we all know the computation
    power of a processor is also limited.
    Assume 1 sec ~ 10^8 operations per
    second . (for SPOJ old server it
    is 4*10^6). Keep this in mind while
    solving any problem.

  • So if A < 10^6 then your solution
    will pass, but here A<10^9, hence it
    is giving ‘Time Limit Exceeded’. Try
    to come with a optimal solution :slight_smile:

  • Hint: This problem has a O(k) solution and k, according to problem statement is < 100 :smiley: