> 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/421.-maximum-xor-of-two-numbers-in-an-array.md).

# 421. Maximum XOR of Two Numbers in an Array

## Problem Statement

<br>

Given an integer array `nums`, return *the maximum result of* `nums[i] XOR nums[j]`, where `0 <= i <= j < n`.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [3,10,5,25,2,8]
</strong><strong>Output: 28
</strong><strong>Explanation: The maximum result is 5 XOR 25 = 28.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
</strong><strong>Output: 127
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 2 * 105`
* `0 <= nums[i] <= 231 - 1`

## Intuition

```
Approach:

Insert all the elements in Trie,
Then, for each element again , 
check if opposite bits exist and move there 

This way you generate answer 


9 -> 1001
Insert from start-> Start bits are valuable for maximum answer
```

### Links

<https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/description/>

### Video Links

<https://www.youtube.com/watch?v=EIhAwfHubE8&list=PLgUwDviBIf0pcIDCZnxhv0LkHf5KzG9zp&index=6&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:
    int findMaximumXOR(vector<int>& nums) {
        Trie trie;
        int ans = 0;
        for(auto &it: nums)
            trie.insert(it);

        for(auto &it: nums)
            ans = max(ans, trie.check(it));

        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

###