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

What do you mean by `maximum xor for two elements`? Wouldnt there be only one possible XOR value for two elements? — thefourtheye, Sep 29 '13 at 06:05
I still dont get it. What is the maximum XOR value of 1 and 2? — thefourtheye, Sep 29 '13 at 06:07
Say we have an array having some elements , and i take every pair of elements and take their XOR , then the maximum of this will be the answer for Two element Maximum XOR. — Mod, Sep 29 '13 at 06:08
Took me a while to digest the question. You should add short explanation what you mean by editing the question, perhaps even a nicely formatted example with a 4-element array, and explain the algorithmic complexity requirement. — hyde, Sep 29 '13 at 07:36
Since you have a solution that solved your purpose, just write a self-answer and accept it. Or change OP to request better time complexity... — Evgeny Kluev, Sep 29 '13 at 10:01

score 6 · Accepted Answer · edited May 23 '17 at 12:21

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.

Other possibility to reduce this to the linked problem would be to fix one element of the array (X), then apply any of the linked algorithms to the values X^A[i], then choose other element for X, etc. — Evgeny Kluev, Sep 29 '13 at 11:55
The same solution (using a trie) could be found here: [CHXORR - Editorial](http://discuss.codechef.com/questions/25276/chxorr-editorial). — Evgeny Kluev, Sep 29 '13 at 13:29

score 0 · Answer 2 · answered Sep 29 '13 at 06:20

0

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;

answered Sep 29 '13 at 06:20

hasan

23,815
10
63
101

Well, thanks for the answer but I already know of the O(N^3) solution I wanted something better complexity. – Mod Sep 29 '13 at 06:23
2 problems here: 1. Since these are logical operations - unsigned should probably be used. 2. It allows xoring the same element more than once, which I believe is not allowed - as an exmple, this will make a case in which one of the elements is 0xffffffff always result in max as xoring it with itself twice always result in 0xffffffff. – Avi Perel Sep 29 '13 at 08:25

Avi Perel · Answer 3 · 2013-09-29T08:52:00.387

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;
}

Three elements in array whose xor is maximum

3 Answers3