# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/trie/1707.-maximum-xor-with-an-element-from-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.