// http://www.codechef.com/problems/DCE05
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;
int main ()
{
int testCase;
scanf ("%d", &testCase);
while ( testCase-- ) {
unsigned int n;
scanf ("%u", &n);
for ( int i = 0; i < 32; i++ ) {
if ( pow (2, i) > n ) {
printf ("%d\n", (int)pow (2, i - 1));
break;
}
}
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

Will please explain your logic about pow of 2 form 1 to 31 ? Thank you.

@ shantanu saha

the idea is pretty simple. it will always follow a sequence

if you do some paper-pen work, its going to be clear to you

For example, if there are 50 people then

1st step:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ………… 44 45 46 47 48 49 50

2nd step:

2 4 6 8 10 12 14 16 18 20 22 24 … 44 46 48 50

3rd step:

4 8 12 16 20 24 28 32 36 40 44 48

4th step:

8 16 24 32 40 48

5th step:

16 32 48

6th step:

32

observe carefully that, if there are 40 people then the result and intermediate steps will be same

in fact, if the input is in the range of 32 to 63 then output is same

output will be, largest power of 2, which is less than or equals to the input

now, if you want to know the internal logic, that would be bit tough for me to explain 😛

after every round, you will get half people than previous round

that means, you are reducing people by 2

after 1st round these people are got out

1 3 5 7 9 11 13 15 17 19 …..

these number do not have prime factor 2

after 1st round we will get:

2 4 6 8 10 12 14 16 18 20 22 24 … 44 46 48 50

these numbers have at least one prime factor 2

2 = 2 * 1

4 = 2 * 2

6 = 2 * 3

8 = 2 * 2 * 2

and so on

after 2nd round we will get:

4 8 12 16 20 24 28 32 36 40 44 48

these numbers have at least two prime factor 2

4 = 2 * 2

8 = 2 * 2 * 2

12 = 2 * 2 * 3

16 = 2 * 2 * 2 * 2

20 = 2 * 2 * 5

and so on

after 3rd round we will get:

8 16 24 32 40 48

these numbers have at least three prime factor 2

8 = 2 * 2 * 2

16 = 2 * 2 * 2 * 2

24 = 2 * 2 * 2 * 3

32 = 2 * 2 * 2 * 2 * 2

and so on

finally you will get the value, which has the highest number of prime factor 2 🙂

hope you get some idea about the solution 🙂

thanks shantanu…could u pls tel me any good books to learn ths kind of logic

@k4v1r4j

learn logic by problem solving

you can read tutorials from Usaco, topcoder, codechef

i’ve heard a lot of about a book: Programming challenges by Steven skiena & Miguel revilla

#include

#include

using namespace std;

int main()

{

int t;

long long int n;

cin>>t;

while(t–)

{

cin>>n;

int k=1;

while(pow(2,k)<n)

{

k++;

}

if(pow(2,k)==n)

cout<<n<<endl;

else

cout<<pow(2,k-1)<<endl;

}

return 0;

}

codechef is not accepting this code. wht is wrong with it. it is giving same answer.