why is this showing TLE

,

can anyone please tell me that why my this code is showing tle

Link : http://www.codechef.com/problems/DCE05

#include<stdio.h>

int main()

{

    int n,i,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int res = n&(n-1);
        if(res==0)
        printf("%d\n",n);
        else
        {
            for(i=n;i>=1;i--)
            {

                res=i&(i-1);
                if(res==0)
                {
                    printf("%d\n",i);
                    break;
                }
            }
        }
    }

    return 0;
}

Edit : Formatted

At least mention the problem or link to the problem you are solving that anyone who reads your code may at least get an idea of what you are trying to implement.

For e.g. : One possibility is that the question you are solving may have large values of n(upto 10^18)…thus a simple loop might not suffice.

sorry for not mentioning the problem
the problem is here

Inner loop in your program runs n times and n can be as big as 10^9.

t is about 10^5

10^5 * 10^9 is too big and hence TLE.

HINT : Try it on all small inputs n (say < 30) and observe the answers.

1 Like

As anudeep pointed out, 10^14 is a huge amount of computations to perform… There’s a very clever approach to solve this problem though :slight_smile:

Best regards,
Bruno

can you please tell me the approach to solve this problem
thanks

Try looking out for the math behind it. When I solved the problem, I too faced the TLE error , but then a simple observation did it for me.

@nishant As i mentioned write down all answers for all values of n from 1 to 33 and you will understand the answer.

The problem boils down to simple calculation of 2^m <= n and printing the 2^m.

I think you know the above part, but you are using naive approach for calculation of m. You are using for loop which starts at n and each time decrements by 1.

Have you thought about case n=1000000000? It will unnecessarily run for 463129088 times! Since, answer is 536870912!

Now think a simpler approach. Initialize int res=1 and use this while loop:

while(res<=n)
{res*=2;}//use res=res<<1 if you want
printf("%d\n",res);

Now, even in the worst case it will run only for 30 times! See the difference between 463129088 and 30!

Else, you can pre-compute all 2^m for m=0 to 31 in an array and just compare with each element until you get 2^m>n and then print arr[m-1]!

how can i find that which technique will be faster
1.using while loop the way you mentioned
or
2. pre-computing all values and than comparing
i submitted my problem using the while loop method and it took 0.78 seconds here is my solution
http://www.codechef.com/viewsolution/1605648
can i optimize it further ??
thanks everyone for answering…:slight_smile:

how can i find that which technique will be faster 1.using while loop the way you mentioned or 2. pre-computing all values and than comparing i submitted my problem using the while loop method and it took 0.78 seconds here is my solution http://www.codechef.com/viewsolution/1605648 can i optimize it further ?? thanks everyone for answering…:slight_smile:

If u pre-compute its one time and so time taken will be time to compute values once and time to answer queries

Pre computing O(1)

Latter is O(log n) if you use binary search.

It can be reduced to O(1) using bit tricks to compute lg n and number of set bits.

On the whole, It is O(t*log n) but can be optimized to O(t);

While Loop Method, What you call as, needs to run a loop for all test cases and so time taken is Time per one test case * number of testcases

It is O(t*log n)

Have you learnt Analysis of Algorithms in your academics? If not, buy a book for it and study it.
As far as I am concerned, I think both of above methods will run in same time. Since, while loop will execute only 1 statement and will run for same number of times. But few things I noticed, when I tried above methods myself.

  1. Using bitwise operations res=res<<1, reduced the time by 0.05s
  2. Using getchar_unlocked() method rather than scanf(), reduced the time by half to 0.34s http://www.codechef.com/viewsolution/1619320
  3. Those who get lower time than this, are not using printf()!

thanks alot for guiding me
i was just looking forward to read design and analysis of algorithms
one more thing
can you please guide me from where i can read about fast input/output routines like getchar_unlocked
also i have seen that programs which took least time always uses buffer in there solution to read input can you please guide me from where i can read about this
i m unable to search them on google
thanks