Maximum XOR of Two Numbers in an Array

Moderate

0/80

Average time to solve is 35m

Contributed by

42 upvotes

Asked in companies

Problem statement

An array ‘A’ of ‘N’ integers is provided. Return the maximum possible number which can be created by taking bitwise XOR of any 2 integers of the array.

Example:

If the array is 2,5 and 6

2 XOR 5 is 7
2 XOR 6 is 4
5 XOR 6 is 3

Hence the answer is 7.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains one integer ‘N’, denoting the size of the array.

The next line contains 'N' space-separated integers representing the elements of 'A'.

Output Format:

Print a single integer in a new line denoting the maximum xor value.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Sample Input 1:

3
2 1 4

Sample Output 1:

Explanation for Sample Input 1:

Select the 1st and 3rd element leading to a xor value of 6.

Sample Input 2:

2
3 2

Sample Output 2:

Constraints:

1 <= N <= 10^4
1 <= A[i] <= 10^9 

Time Limit: 1 sec

Hint 1

Hint 2

Can we check all possible combinations of taking two indexes?

Approaches (2)

Approach 1

Approach 2

Brute Force

To find the maximum possible among all such pairs, we can use two nested loops to check all possible pairs and store the maximum possible xor value.

Algorithm:

Initialise ‘ans’ to 0.
Run a loop ‘i’ from 0 to ‘N’ - 1
- Run a loop ‘j’ from ‘i’ to ‘N’ - 1
- Update ‘ans’ to the maximum of ‘ans’ and ‘A[i]’ xor ‘A[j]’
Return ‘ans’’

Time Complexity

O(N ^ 2), where ‘N’ is the size of the array.

Since we are using two nested loops to find all possible pairs, so the total time complexity is O(N ^ 2).

Space Complexity

O(1)

We are using constant extra space.

(75% EXP penalty)

(100% EXP penalty)

Maximum XOR of Two Numbers in an Array

Console