CodeChef : Odd (DCE05)



// 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

5 thoughts on “CodeChef : Odd (DCE05)

  1. @ 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 🙂

  2. @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

  3. #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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s