INQU2000 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Ashish Chaudhary

DIFFICULTY:

Easy

PROBLEM:

You are given a number X. You have to choose a number Y(greater than or equal to X) such that taking XOR of any number from 1 to X-1 with Y always results in a number greater than Y.
Print the minimum possible value of Y.

EXPLANATION:

For every number N, which is a power of 2, has only one bit set in its binary representation,i.e. MSB. Even if we take the XOR of N with any number from 1 to N-1, it has no effect on the most significant bit of N.
So smallest power of 2 which is greater than or equal to X is the desired answer.

SOLUTION:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main()
{
    boost
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll cn=n;
        ll co=0;
        while(n!=0)
        {
            n/=2;
            co++;
        }
        if((1LL<<(co-1))==cn)
        {
            cout<<cn<<endl;
        }
        else
            cout<<(1LL<<co)<<endl;
    }
    return 0;
}