> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/trie/1707.-maximum-xor-with-an-element-from-array.md).

# 1707. Maximum XOR With an Element From Array

## Problem Statement

<br>

You are given an array `nums` consisting of non-negative integers. You are also given a `queries` array, where `queries[i] = [xi, mi]`.

The answer to the `ith` query is the maximum bitwise `XOR` value of `xi` and any element of `nums` that does not exceed `mi`. In other words, the answer is `max(nums[j] XOR xi)` for all `j` such that `nums[j] <= mi`. If all elements in `nums` are larger than `mi`, then the answer is `-1`.

Return *an integer array* `answer` *where* `answer.length == queries.length` *and* `answer[i]` *is the answer to the* `ith` *query.*

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
</strong><strong>Output: [3,3,7]
</strong><strong>Explanation:
</strong>1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
</strong><strong>Output: [15,-1,5]
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length, queries.length <= 105`
* `queries[i].length == 2`
* `0 <= nums[j], xi, mi <= 109`

## Intuition

```
Approach:

We cannot Brute force and do repetative Xor operations

So, We sort the array based on the queries[i][1] which is cap
This will allow us to iterativelt at each step 

Build the trie and check (offline queries approach)
0 1 2 3 4 
1) Now 12,1
Build for 0 1
Check for 12
2) Now, 13,2
Just add 2 and check 13

So on as 0 and 1 already added
```

### Links

<https://leetcode.com/problems/maximum-xor-with-an-element-from-array/description/>

### Video Links

<https://www.youtube.com/watch?v=Q8LhG9Pi5KM&list=PLgUwDviBIf0pcIDCZnxhv0LkHf5KzG9zp&index=7&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
struct Node{
    Node* links[2];
};

class Trie{
public:
    Node * root = new Node();

    void insert(int num){
        Node *temp = root;
        for(int i=31; i>=0; i--){
            int bit = (num>>i) & 1;
            if(temp->links[bit] == nullptr)
                temp->links[bit] = new Node();
            
            temp = temp->links[bit];
        }
    }
    
    int check(int num){
        Node* temp = root;
        int ans = 0;
        for(int i=31; i>=0; i--){
            int bit = (num>>i) & 1;
            if(temp->links[1-bit] == nullptr){
                temp = temp->links[bit];
            }
            else{
                temp = temp->links[1-bit];
                ans = ans | 1<<i;
            }
        }

        return ans;
    }
};

class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        Trie trie;

        vector<int> ans(queries.size());
        sort(nums.begin(), nums.end());
        vector<vector<int>> sort_q;
        // Contains -> cap, actual_num, index
        for(int i=0; i<queries.size(); i++)
            sort_q.push_back({queries[i][1], queries[i][0], i});
        
        sort(sort_q.begin(), sort_q.end());
        for(auto &it: sort_q)
            cout<<it[0]<<" "<<it[1]<<" "<<it[2]<<endl;

        int i=0, j=0;
        while(j<sort_q.size()){
            int cap = sort_q[j][0];
            int num = sort_q[j][1];
            int index = sort_q[j][2];
            if(cap < nums[0])
                ans[index] = -1;

            else{
                while(nums[i] <= cap and i<nums.size()){
                    trie.insert(nums[i]);
                    i++;
                }

                ans[index] = trie.check(num);
            }
            j++;
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###