Problem Statement

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

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

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

Problem Link

Maximum XOR of Two Numbers in an Array - LeetCode

Code (Using Trie)

class Solution {
public:
    struct Trienode
    {
        Trienode *child[2];
        
        Trienode()
        {
            child[0] = child[1] = NULL;
        }
    };
    
    Trienode *root;
    Solution()
    {
        root = new Trienode();
    }
    
    void insert(int num)
    {
        Trienode *curr = root;
        
        for(int i=31;i>=0;i--)
        {
            int bit = (num>>i)&1;
            
            if(!curr->child[bit])
                curr->child[bit] = new Trienode;
            
            curr = curr->child[bit];
        }
        
        
    }
    
    int findmaxXor(int num)
    {
        Trienode *curr = root;
        int maxXor = 0;
        
        for(int i=31;i>=0;i--)
        {
            int bit = (num>>i)&1;
            
            if(curr->child[1-bit])
            {
                 curr = curr->child[1-bit];
                 maxXor+=pow(2,i);       
            }
            else
                curr = curr->child[bit];
            
        }
        
        return maxXor;
    }
    int findMaximumXOR(vector<int>& nums) {
        
        int n = nums.size();
        
        for(int num:nums)
        {
            insert(num);
        }
        
        int res = 0;
        
        for(int num:nums)
        {
            res = max(res,findmaxXor(num));
        }
        
        return res;
        
    }
};