C++ gurus help me out

[nims11]

i am trying to solve this easy problem at codechef.comOdd | CodeChef
i have made a really short program to solve it. it gives correct answers when i test. but it exceeds the time limit in the codechef servers.
my code is

#include<iostream>
#include <cmath>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int a;
cin>>a;
cout<<(int)pow(2,(float)((int)log2(a)))<<endl;
}
return 0;
}

suggestions plz....

 

[Sid]

Well looking at the code, the only thing visible to me is to reduce the casting that is used.

However, i noticed that the reason you get the right answer is because of the casting. As you cast, you lose the precision and you come close to the approximate answer.

This was my analysis, you can try building upon it.

--- as per your code, after removing the casts, the answer is.
= 2 ^ ( log2(a) )
= 2 ^ ( log10(a) / log10(2) )
= ( 2 ^ ( 1 / log10(2) ) ) ^ log10(a)

Now,
( 2 ^ ( 1 / log10(2) ) ) = 10

However, if i apply the casting to lose the precision then,
( 2 ^ ( 1 / log10(2) ) ) = 8

Therefore, your answer is
= 8 ^ log10(a).

Therefore finally in your code you may do this,

float a;
cin>>a;
cout<<(int)pow(8, log10(a));

Hopefully this might help.
Also, i don't think using { 8 ^ log10(a) } might give you right answer for all inputs. I believe a value between 7 and 8 ought to give you the right answer. Do find that out. If you can't then you might find yourself righting extra code to handle that part.

Other than this, i have no idea how we can improve the time complexity of your code.

What i may suggest is that write the same code in java or c#, and check whether there too your code consumes more than allowed time, as finally, in today's faster CPUs this use casting, pow & log functions cost a negligible extra time.