Page Contents
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
- Longest AND Subarray
- MEX-OR
- Digit Removal
- Yet another MEX problem
- Characteristic Polynomial Verification
- Chef at the Olympics
- Which Mixture
- Three Boxes