Three elements in array whose xor is maximum

Question

I want to know a algorithm to find out the maximum xor value of three elements of an array. I have read about the maximum xor for two elements from an array but cannot understand how to apply it on finding the maximum value of XOR taking 3 elements of an array . Can someone point out a hint ?

Required complexity : less than O(N^3) where N is the number of elements in the array.

Example:

A = [1,2,3,4]

All Possible Triplets :-

1^2^3 = 0
1^2^4 = 7
1^3^4 = 6
2^3^4 = 5

Thus, the maximum XOR value is 7.

Edit :

I have thought of a solution having complexity O(N^2 * log(MAX)) and it has solved my purpose :D .

MAX = Maximum Value in the Array

Answer 1

Well, I have found a solution with complexity O(N^2 * log(MAX)) where MAX is the largest value in the array .

Let there be 3 elements X,Y,Z fron the array A.

where X = A[i] , Y = A[j] , Z = A[k] and i != j != k

We want the maximum value of (X^Y^Z) .

Let us assume W = X*Y.

Then we would like to find such a Z which give maximum value for W^Z and Z != X and Z != Y

Now this has been reduced to the problem of finding "Two elements whose XOR is maximum" which can be done for a given W in O(log(MAX)) using a Trie .

Explanation for Trie :

Let us assume W = 10001 here W is in binary .

Now we know 1^0 = 1 , 0^0 = 0 , 1^1 = 0 , so the maximum value we can get for W^Z is when Z is 01110 because W^Z will give = 11111.

But it is not necessary to have 15 or Base2(11111) in our array so we would take the best possible option available.

So we will create a Trie of all the elements of the array according to their binary representation.

If A = [1,2,7] , then 1 = 001 , 2 = 010 , 7 = 111 in binary .

Then the Trie will look like :-

                            Top
                           /   \
                          0     1
                         / \     \
                        0   1     1
                         \ /       \
                         1 0        1

Now to lets assume W = 7 , and we want to find Z such that W^Z is maximum (when Z = 000 ) then we will start at the Top and look if we have branch leading to 0 since the first bit of 7 is 1 , then we will down through that branch and then again look if we have branch leading to 0 at 2nd bit , again we find it , then for the last time we search for branch leading to a 0 at 3rd bit but we do not find it , so we go down through the other branch which gives us Z = 001. Thus, the maximum W^Z will be 7^1 = 6 . Now , the complexity of finding Z will be maximum height of the Trie which will be log(MAX).

Thus , we have N*(N-1)/2 number of W's and for each W we can find the Maximum value of W^Z and if we take the Maximum from all the values of W^Z we will have our answer.