# C++ solution O(n) segregating by bits

• So I keep vector of pairs of vectors :
for each pair of vectors
for each number taken from the first vector
for each number taken from the second vector
xoring x most significant bits gives the best result

Constant is brutal, but it's O(n) nonetheless.

``````class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
function<pair<vector<int>,vector<int>>(vector<int>&, int)> segregate =
[&](vector<int> &inp, int bit){
vector<int> res1;
vector<int> res2;
for(int a: inp){
if(a & bit){
res2.push_back(a);
} else{
res1.push_back(a);
}
}
return make_pair(res1, res2);
};
if(nums.size() <= 1){
return 0;
}
int bit;
typedef vector<int> VI;
vector<pair<VI,VI>> res;
for(bit = 31; bit >= 0; bit--){
pair<VI,VI> p = segregate(nums, 1 << bit);
if(!p.first.empty() && !p.second.empty()){
res.push_back(p);
bit--;
break;
}
}
if(res.empty()){
return 0;
}
for(;bit >= 0; bit--){
vector<pair<VI,VI>> res2;
for(pair<VI,VI> & p: res){
pair<VI,VI> seg1 = segregate(p.first, 1 << bit);
pair<VI,VI> seg2 = segregate(p.second, 1 << bit);
for(int i = 0; i < 2; i++){
if(!seg1.first.empty() && !seg2.second.empty()){
res2.push_back({seg1.first, seg2.second});
}
swap(seg1, seg2);
}
}
if(!res2.empty()){
swap(res, res2);
}
}
pair<VI,VI> last = res.back();
return last.first[0]^last.second[0];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.