Maximum XOR of Two Numbers in an Array

Problem: Given an array nums of integers. Find the maximum possible xor between two numbers present in the array that is the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n

Example:

Input: nums = [1,2,3,4]
Output: 7
Explanation: The maximum result is 3 XOR 4 = 7.

Approach: We can use the brute force approach but it will take O(n^2) time. Let's try to find a better solution.

Let's think what could be the maximum XOR. The maximum XOR is a number which contains all the set bits. Right so what we can do is we can start with max = 10000...00 (30 times) and see if there are two elements whose XOR is max. Say we found it.

Then we can look at 110000....0000(29 times) as max and see if there are two elements whose XOR is this new max. Say we found it then the next max will be 111000....0000(28 times) otherwise the next max will be 1010000...000(28 times). We will keep doing the same till we reach the end. That is when we reach the least significant bits or we do it 31 times.

To check whether there are two numbers whose XOR is max, we can take the help of hashing. That's all!

  

Implementation in C#:

        public int FindMaximumXOR(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return 0;

            }

            int max = 0;

            int mask = 0;           

            for (int i = 30; i >= 0; --i)

            {

                HashSet<int> hash = new HashSet<int>();

                mask |= (1 << i);

                foreach(int num in nums)

                {

                    hash.Add(num & mask);

                }

                int newMax = max | (1 << i);

                foreach(int prefix in hash)

                {

                    if (hash.Contains(newMax ^ prefix))

                    {

                        max = newMax;

                        break;

                    }

                }

            }

            return max;

        }

Complexity: O(31*n) = O(n)