October Long Challenge MEX-OR MEXOR

by

October Long Challenge MEX-OR MEXOR

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 00, because 00 does not belong to the array.
  • The MEX of [3,1,0,1][3,1,0,1] is 22, because 00 and 11 belong to the array, but 22 does not.
  • The MEX of [0,3,1,2][0,3,1,2] is 4 because 0,1,20,1,2 and 33 belong to the array, but 44 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 XX.

Input Format

  • The first line contains TT denoting the number of test cases. Then the test cases follow.
  • Each test case contains a single integer XX 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≤1051≤T≤105
  • 0≤X≤1090≤X≤109

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 11: The array could be [0][0].

Test case 22: The array could be [0,1][0,1]. Here the bitwise OR of 00 and 11 is 11 and the MEX of the array is 22 as both 00 and 11 belongs to the array.

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

CLICK BELOW!!

Solution

Program C++:

#include <iostream>
#include<cmath>
using namespace std;

int main() {
  // your code goes here
  int t; cin>>t;
  while(t--){
      int m;
      cin>>m;
      bool flag=true;
      int count=0,x=m;
      if(x==0){
      cout<<"1"<<endl;
      continue;
      }
      while(x!=0)
      {
          int l=x%2;
          if(l==0)
          flag=false;
          
          x/=2;
          count++;
      }
     
      if(flag) 
      cout<<m+1<<endl;
       else{
          int sum=0;
          count--;
          while(count--){
              sum+=pow(2,count);
          }
          cout<<sum+1<<endl;
      }
  }
  return 0;
}

October Long Challenge 2021

Leave a Comment