Algorithm
Alice gave Bob two integers a and b (a>0 and b≥0). Being a curious boy, Bob wrote down an array of non-negative integers with MEX value of all elements equal to a and XOR value of all elements equal to b.
What is the shortest possible length of the array Bob wrote?
Recall that the MEX (Minimum EXcluded) of an array is the minimum non-negative integer that does not belong to the array and the XOR of an array is the bitwise XOR of all the elements of the array.
The input consists of multiple test cases. The first line contains an integer t (1≤t≤5⋅104) — the number of test cases. The description of the test cases follows.
The only line of each test case contains two integers a and b (1≤a≤3⋅105; 0≤b≤3⋅105) — the MEX and XOR of the array, respectively.
For each test case, output one (positive) integer — the length of the shortest array with MEX a and XOR b. We can show that such an array always exists.
5 1 1 2 1 2 0 1 10000 2 10000
3 2 3 2 3
In the first test case, one of the shortest arrays with MEX 1 and XOR 1 is [0,2020,2021].
In the second test case, one of the shortest arrays with MEX 2 and XOR 1 is [0,1].
It can be shown that these arrays are the shortest arrays possible.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
int a, b;
cin>>a>>b;
int res, n = a - 1;
if(n % 4 == 0){
res = n;
}
else if(n % 4 == 1){
res = 1;
}
else if(n % 4 == 2){
res = n + 1;
}
else{
res = 0;
}
if(res == b){
cout<<a<<endl;
}
else{
if((res ^ b) != a){
cout<<(a + 1)<<endl;
}
else{
cout<<(a + 2)<<endl;
}
}
}
}Input
1 1
2 1
2 0
1 10000
2 10000
Output
2
3
2
3
Demonstration
Codeforcess Solution 1567-B B. MEXor Mixup ,C++, Java, Js and Python ,1567-B,Codeforcess Solution