# Force buckle 1707 - the maximum XOR value of the element in the array

Key points of algorithm:

• 01Trie
• Offline query and online query
• 01some statistical information of subtree can be additionally maintained in trie node

## \$1 title

### Title Description

Give you an array of nonnegative integers, nums. There is also a query array queries, where queries[i] = [xi, mi].

The answer to the ith query is the maximum value obtained by bitwise XOR (XOR) of xi and any element in the num array that does not exceed mi. In other words, the answer is max (Num [J] XOR xi), where all j satisfy num [J] < = mi. If all elements in nums are greater than mi, the final answer is - 1.

```Tips:
1 <= nums.length, queries.length <= 1e5
queries[i].length == 2
0 <= nums[j], xi, mi <= 1e9
```

### Sample

Example 1:
Input: num = [0,1,2,3,4], queries = [[3,1], [1,3], [5,6]]
Output: [3,3,7]
Explanation:

1. 0 and 1 are the only two integers that do not exceed 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The greater of the two is 3.
2. 1 XOR 2 = 3.
3. 5 XOR 2 = 7.

Example 2:
Input: num = [5,2,4,6,6,3], queries = [[12,4], [8,1], [6,3]]
Output: [15, - 1,5]

## \$2 solution

If mi is not exceeded, the problem becomes to find the maximum XOR value for a given xi. This is a basic problem solved by 01Trie, which can be referred to 01Trie This article.

### Algorithm: 01Trie + offline query

Given all the query questions directly, we can use the idea of offline, that is, reasonably adjust the order of answering queries, so as to reduce the time complexity.

Sort all numbers of nums, and then sort the query q = (x, m) from small to large by M

Enumeration query qi = (xi, mi). First, insert all numbers less than or equal to mi in num into 01Trie. This process can maintain a pointer on num and insert only the part after the pointer. After the insertion is completed, the maximum XOR value of the inserted number in xi and 01Trie is the answer to the query.

#### code

Note: if the following code changes the dictionary tree definition Trie01 *trie = Trie01() to Trie01 trie, and changes trie01 - > insert() and trie01 - > search() to trie01 Insert() and trie01 Search(), the running time will and time out, which is increased by 4 times after testing.

Dictionary tree direct use 01Trie Templates in.

```struct Query
{
int idx;
int xi;
int mi;
Query(int i, int xi, int mi):idx(i),xi(xi),mi(mi){}
bool operator<(const Query& q) const
{
return mi < q.mi;
}
};

class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
int m = queries.size();
sort(nums.begin(), nums.end());
vector<Query> qs;
for(int i = 0; i < m; ++i)
qs.emplace_back(i, queries[i][0], queries[i][1]);
sort(qs.begin(), qs.end());
Trie01 *trie01 = new Trie01();
vector<int> result(m);
int iter = 0;
for(int j = 0; j < m; ++j)
{
while(iter < n && nums[iter] <= qs[j].mi)
{
trie01 -> insert(nums[iter]);
++iter;
}
result[qs[j].idx] = trie01 -> search(qs[j].xi);
}
return result;
}
};
```

### Algorithm: 01Trie + online query

On the basis of conventional 01Trie, add a minx field to the node to represent the minimum value of the number on the subtree with the node as the root. This information is needed when processing queries online.

First insert all numbers into 01Trie, and then process each query in turn.

For each query q[i] = (xi, mi), find the value with the largest XOR with xi in the built Trie01. The process is as follows:

```Start from the root and go to the leaves iter Maintenance process
current iter It should always be a guarantee iter -> minx <= mi Yes, you need to judge at this time iter Which direction should I go
if xi The current bit of is 1:
You'd better go to the left subtree: If there is a left subtree, go to the left subtree, otherwise go to the right subtree
if xi The current bit of is 0:
You'd better go to the right subtree: There is a right subtree, and the minimum value of the right subtree <= miļ¼Then go to the right subtree, otherwise go to the left subtree
```

#### code

Trie01 needs to be modified on the basis of the conventional template. The code is as follows

```struct Trie01Node
{
Trie01Node *left, *right;
int minx;
Trie01Node(int minx=INT_MAX)
{
left = nullptr, right = nullptr;
this -> minx = minx;
}
~Trie01Node(){}
};

class Trie01
{
public:
Trie01()
{
root = new Trie01Node();
}

~Trie01()
{
if(root)
{
delete_subtree(root);
}
}

void insert(int num)
{
Trie01Node *iter = root;
iter -> minx = min(iter -> minx, num);
// Enumeration from high to low
for(int i = 30; i >= 0; --i)
{
if((num >> i) & 1)
{
if(!iter -> right)
iter -> right = new Trie01Node();
iter = iter -> right;
}
else
{
if(!iter -> left)
iter -> left = new Trie01Node();
iter = iter -> left;
}
iter -> minx = min(iter -> minx, num);
}
}

bool empty() const
{
if(!root)
return true;
if(!root -> left && !root -> right)
return true;
return false;
}

int search(int x, int mi)
{
if(empty())
return -1;
/*
* Given x, find a that maximizes x ^ a
* Try to make the x on the high position different from a
* All the numbers are 30 in length
*/
Trie01Node *iter = root;
if(iter -> minx > mi)
return -1;
int a = 0;
for(int i = 30; i >= 0; --i)
{
if((x >> i) & 1)
{
if(iter -> left)
iter = iter -> left;
else
{
iter = iter -> right;
a |= (1 << i);
}
}
else
{
if(iter -> right && iter -> right -> minx <= mi)
{
iter = iter -> right;
a |= (1 << i);
}
else
iter = iter -> left;
}
}
return a ^ x;
}

private:
Trie01Node *root;

void delete_subtree(Trie01Node* node)
{
if(node -> left)
delete_subtree(node -> left);
if(node -> right)
delete_subtree(node -> right);
delete node;
node = nullptr;
}
};

class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
int m = queries.size();
Trie01 *trie01 = new Trie01();
for(int x: nums) trie01 -> insert(x);
vector<int> result(m);
for(int i = 0; i < m; ++i)
{
result[i] = trie01 -> search(queries[i][0], queries[i][1]);
}
return result;
}
};
```

Keywords: data structure leetcode

Added by FlashbackJon on Tue, 08 Feb 2022 15:54:10 +0200