MEX-OR Solution - Codechef

 

Video Approach:

Read problem statements.

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of [2,2,1]$[2,2,1]$ is 0$0$, because 0$0$ does not belong to the array.
• The MEX of [3,1,0,1]$[3,1,0,1]$ is 2$2$, because 0$0$ and 1$1$ belong to the array, but 2$2$ does not.
• The MEX of [0,3,1,2]$[0,3,1,2]$ is 4 because 0,1,2$0,1,2$ and 3$3$ belong to the array, but 4$4$ does not.

Find the maximum possible MEX of an array of non-negative integers such that the bitwise OR of the elements in the array does not exceed X$X$.

Input Format

• The first line contains T$T$ denoting the number of test cases. Then the test cases follow.
• Each test case contains a single integer X$X$ on a single line.

Output Format

For each test case, output on a single line the maximum possible MEX of the array satisfying the given property.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 0≤X≤109$0\le X\le {10}^9$

Subtasks

Subtask 1 (100 points): Original constraints

Sample Input 1 

4
0
1
2
5

Sample Output 1 

1
2
2
4

Explanation

Test case 1$1$: The array could be [0]$[0]$.

Test case 2$2$: The array could be [0,1]$[0,1]$. Here the bitwise OR of 0$0$ and 1$1$ is 1$1$ and the MEX of the array is 2$2$ as both 0$0$ and 1$1$ belong to the array.

Test case 4$4$: The array could be [1,0,3,2]$[1,0,3,2]$. Here the bitwise OR of all integers in the array is 3$3$ and the MEX of the array is 4$4$.

MEX-OR Solution: 

#include <iostream>

using namespace std;

int main() {

// your code goes here

int t;

cin>>t;

while(t--){

    int x, ans = 1;

    cin>>x;

    if(x == 0){

        cout<<1<<endl;

    }

    else if(x == 1 || x == 2){

        cout<<2<<endl;

    }

    else{

        while(ans*2 <= x){

            ans*=2;

        }

        if(ans == x){

            cout<<x<<endl;

        }

        else if(x ==(2*ans-1)){

            cout<<x+1<<endl;

        }

        else{

            cout<<ans<<endl;

        }

    }

}

return 0;

}