Maximum XOR of Two Numbers in an Array

Companies:
  • Amazon Interview Questions
  • Microsoft Interview Questions

Problem Statement

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ ij < n.

Sample Test Cases

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

Problem Solution

The Approach is that instead of finding the maximum XOR of two numbers in an array, we can find two numbers in an array such that XOR of the numbers equal to a number X.

In this case, X will be the maximum number we want to achieve till i-th bit.

To find the largest value of an XOR operation, the value of xor should have every bit to be a set bit i.e 1. In a 32 bit number, the goal is to get the most 1 set starting from left to right.

So to evaluate the bits, there is mask required for each bit. A mask will define which bit should be present in the answer and which bit should not.

Here we will use mask to keep the prefix for every number ( means by taking the ans with the mask how many bits are remaining from the number ) in the input till the i-th bit then with the list of possible numbers in our set, after inserting the number we will evaluate if we can update the max for that bit position to be 1.

Complexity Analysis

Time Complexity :O(N logM) where N is the size of the array and M is the maximum number present in the array.

Space Complexity: O(N) since we are storing in set, worst case scenario could be that ever number is unique.

Code Implementation

#include <bits/stdc++.h>
using namespace std;

// Function to return the
// maximum xor
int findMaximumXOR(vector<int> nums) {

        int mask = 0;
        int result = 0;
        for (int i=30; i>=0; i--)
        {
            mask =  mask | (1 << i);
            set<int>myset;
            for (int i=0; i<nums.size(); i++)
            {
                myset.insert(nums[i] & mask);
            }

            int candidate = result | (1<<i);
            for (auto it=myset.begin(); it!=myset.end(); it++)
            {
                if (myset.count(candidate ^ *it))
                {
                    result = candidate;
                    break;
                }
            }
        }

        return result;

    }


int main()
{

    vector<int>x;
    x.push_back(3);
    x.push_back(10);
    x.push_back(5);
    x.push_back(25);
    x.push_back(2);
    x.push_back(8);

    cout << max_xor(x) << endl;

    return 0;
}

 

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]