In this Leetcode Maximum XOR of Two Numbers in an Array problem solution we have given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Leetcode Maximum XOR of Two Numbers in an Array problem solution


Problem solution in Python.

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        mask = 0
        ans = 0
        
        for i in range(31, -1, -1):
            mask = mask | 1 << i
            s = set()
            for num in nums:
                s.add(num & mask)
            
            start = ans | 1 << i
            
            for prefix in s:
                if start ^ prefix in s:
                    ans = start
        return ans


Problem solution in Java.

class Solution {
    public int findMaximumXOR(int[] nums) {
        Node root = new Node();
        insert(root, nums[0], 30);
        int ans = 0;
        for(int i=1;i<nums.length;i++){
            ans = Math.max(ans, query(root, nums[i], 30));
            insert(root, nums[i], 30);
        }
        return ans;
    }
    public class Node{
        Node left, right;
        int lc, rc;
        public Node(){
            this.left = null;
            this.right = null;
            this.lc = 0;
            this.rc = 0;
        }
    }
    
    void insert(Node node, int val, int level){
        if(level==-1){
            return;
        }
        
        if((val&(1<<level))>0){
            if(node.right==null){
                node.right = new Node();
            }
            node.rc++;
            insert(node.right, val, level-1);
        }else{
            if(node.left==null){
                node.left = new Node();
            }
            node.lc++;
            insert(node.left, val, level-1);
        }
    }
    int query(Node node, int val, int level){
        if(level==-1){
            return 0;
        }
        
        if((val&(1<<level))>0){
            if(node.left!=null){
                return query(node.left, val, level-1)|(1<<level);
            }else{
                return query(node.right, val, level-1);
            }
        }else{
            if(node.right!=null){
                return query(node.right, val, level-1)|(1<<level);
            }else{
                return query(node.left, val, level-1);
            }
        }
    }
}


Problem solution in C++.

#define ll long long
class Solution {
public:
    
    struct Tries{
        array<Tries *, 2> mp;
    };

    void insert(Tries *root, int n){
        for(int i=31; i>=0; i--){
            int bit = (n&(1<<i));
            if(bit) bit = 1;
            if(root->mp[bit] == NULL)
                root->mp[bit] = new Tries();
            root = root->mp[bit];
        }
    }

    ll findMax(Tries *root, ll n){
        ll ans = 0;
        for(int i=31; i>=0; i--){
            int bit = (n&(1<<i));
            if(bit) bit = 1;
            if(root->mp[!bit]){
                ans += (1<<i);
                root = root->mp[!bit];
            }
            else
                root = root->mp[bit];
        }
        return ans;
    }
    
    int findMaximumXOR(vector<int>& nums) {
        int ans = 0;
        Tries *root = new Tries();
        for(int i : nums)
            insert(root, i);
        for(int i : nums){
            int x = findMax(root, i);
            ans = max(ans, x);
        }
        return ans;
    }
};


Problem solution in C.

#define MAX_BIT 30
struct tree{
    struct tree *leaf[2]; /* bit 0 --> leaf 0 ; bit 1 --> leaf 1*/
};


static void buildTree(struct tree *root, int *nums, int numsSize)
{
    int i;
    int j;
    int bit_val;
    struct tree *node = NULL;

    for (i = 0; i < numsSize; i++) {
        node = root;
        for (j = MAX_BIT; j >= 0; j--) {
            bit_val = nums[i] >> j & 1;
            if (!node->leaf[bit_val])
                node->leaf[bit_val] = calloc(1, sizeof(*root));
            node = node->leaf[bit_val];
        }
    }
}

void freeTree(struct tree *root)
{
    if (!root)
        return;
    
    if (root->leaf[0]);
        freeTree(root->leaf[0]);
    if (root->leaf[1])
        freeTree(root->leaf[1]);
    free(root);
}

int findMaximumXOR(int* nums, int numsSize)
{
    struct tree root = {0};
    int i;
    int j;
    struct tree *node = NULL;
    int max = 0;
    int cur = 0;
    int bit_val = 0;

    if (1 == numsSize)
        return 0;

    buildTree(&root, nums, numsSize);

    for (i = 0; i < numsSize; i++) {
        cur = 0;
        node = &root;
        for (j = MAX_BIT; j >= 0; j--) {
            bit_val = nums[i] >> j & 1;
            if (node->leaf[!bit_val]) {
                cur += 1 << j;
                node = node->leaf[!bit_val];
            } else {
                node = node->leaf[bit_val];
            }
        }

        if (cur > max)
            max = cur;
    }

    freeTree(root.leaf[0]);
    freeTree(root.leaf[1]);
    return max;
}