Maximum XOR of Two Numbers in an Array LeetCode Solution

Problem – Maximum XOR of Two Numbers in an Array

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 = [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

Maximum XOR of Two Numbers in an Array LeetCode Solution in Java

public class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for(int i = 31; i >= 0; i--){
            mask = mask | (1 << i);
            Set<Integer> set = new HashSet<>();
            for(int num : nums){
                set.add(num & mask);
            }
            int tmp = max | (1 << i);
            for(int prefix : set){
                if(set.contains(tmp ^ prefix)) {
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }
}

Maximum XOR of Two Numbers in an Array LeetCode Solution in Python

def findMaximumXOR(self, nums):
    answer = 0
    for i in range(32)[::-1]:
        answer <<= 1
        prefixes = {num >> i for num in nums}
        answer += any(answer^1 ^ p in prefixes for p in prefixes)
    return answer

Maximum XOR of Two Numbers in an Array LeetCode Solution in C++

int findMaximumXOR(vector<int>& nums) {
        int n = nums.size();
        
        if (n == 0 || n == 1)
            return 0;
        if (n == 2)
            return nums.at(0) ^ nums.at(1);
        
        list<int> set0;
        list<int> set1;
        int i;
        int j;
        int maxValue;
        
        for (i = 30; i >= 0; i--) {
            for (j = 0; j < n; j++) {
                if ((nums.at(j) & (1<<i)) == 0)
                    set0.push_back(nums.at(j));
                else
                    set1.push_back(nums.at(j));
            }
            
            if (set0.size() != 0 && set1.size() != 0) {
                maxValue = pow(2, i);
                break;
            }
            else {
                set0.clear();
                set1.clear();
            }
        }
        
        if (i == -1)
            return 0;
        
        maxValue += getMaxXor(set0, set1, i-1);
        
        return maxValue;
}

int getMaxXor(list<int>& set0, list<int>& set1, int pos) {
        int maxValue;
        list<int> set0list0;
        list<int> set0list1;
        list<int> set1list0;
        list<int> set1list1;
        int i;
        list<int>::iterator it;
        
        if (set0.size() == 0 || set1.size() == 0 || pos < 0)
            return 0;
        
        for (it = set0.begin(); it != set0.end(); it++) {
            int value = *it;
            if ((value & (1<<pos)) == 0)
                set0list0.push_back(value);
            else
                set0list1.push_back(value);
        }
        
        for (it = set1.begin(); it != set1.end(); it++) {
            int value = *it;
            if ((value & (1<<pos)) == 0)
                set1list0.push_back(value);
            else
                set1list1.push_back(value);
        }
        
        if (set0list0.size() == 0 && set1list0.size() == 0)
            maxValue = getMaxXor(set0, set1, pos-1);
        else if (set0list1.size() == 0 && set1list1.size() == 0)
            maxValue = getMaxXor(set0, set1, pos-1);
        else {
            int maxValue1 = getMaxXor(set0list0, set1list1, pos-1);
            int maxValue2 = getMaxXor(set0list1, set1list0, pos-1);
            maxValue = pow(2, pos) + (maxValue1 > maxValue2 ? maxValue1 : maxValue2);
        }
        
        return maxValue;
 }
Maximum XOR of Two Numbers in an Array LeetCode Solution Review:

In our experience, we suggest you solve this Maximum XOR of Two Numbers in an Array LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximum XOR of Two Numbers in an Array LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Maximum XOR of Two Numbers in an Array LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.