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 CodeChef: Practical coding for everyone can i optimize it further ?? thanks everyone for answering…
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.
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…
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.
Using bitwise operations res=res<<1, reduced the time by 0.05s
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