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.

Answer 2

following will do the O(N^3), but in an more optimized approach - not testing same combination more than once, not testing element against itself, and somewhat optimized evaluation (xoring the first two elements once for all possible third elements)

Number of Xor operations performed will be: n(n-1)(n-2)/6 + n(n-1)/2

Complexity is still n(n-1)(n-2)/6 ===> O(N^3) though.

unsigned int maxXor3(unsigned int* element, int len)
{
    unsigned int max = 0;
    unsigned int xor2 = 0;
    unsigned int xor3 = 0;
    int j = k = 0;

    for (int i = 0 ; i < len ; i++)
    {
        for (j = i + 1 ; j < len ; j++)
        {
            xor2 = element[i] ^ element[j];
            for(k = j + 1; k < len; k++)
            {
                xor3 = xor2 ^ element[k];
                if (xor3 > max)
                    max = xor3;
            }
        }
    }
    return max;
}

Answer 3

With three nested loop:

int max2=0,max3=0;
for (int i=0;i<arr.size();i++)
    for (int j=0;j<arr.size();j++)
        for (int k=0;k<arr.size();k++)
        {
            if (arr[i]^arr[j]>max2) // for 2 elements
               max2 = arr[i]^arr[j];
            if (arr[i]^arr[j]^arr[k]>max3) // for 3 elements
               max3 = arr[i]^arr[j]^arr[k];
        }

int max = max2; // for both
if (max3>max2)
   max = max3;