Three elements in the array whose xor are max

Question

I want to know the algorithm to find out the maximum xor value of three elements of an array. I read about the maximum xor for two elements from the array, but I can’t figure out how to apply it when finding the maximum XOR value, taking 3 elements of the array. Can someone give 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 thought of a solution having O (N ^ 2 * log (MAX)) complexity, and he solved my goal: D.

MAX = The maximum value in the array

Answer 1

Well, I 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 from array A.

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

We need the maximum value (X ^ Y ^ Z) .

Suppose W = X * Y.

Then we would like to find a Z that gives the maximum value for W ^ Z and Z! = X and Z! = Y

Now this is 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 Trie .

Explanation for Trie:

Suppose W = 10001 here is W in binary .

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

But in our array there is no need to have 15 or Base2 (11111) . we will use the best option possible.

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

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

Then Trie will look like this: -

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

Now let's assume W = 7 , and we want to find Z that W ^ Z is maximal (at Z = 000) , then we start with Top and see if there is a branch leading to 0, since the first bit of 7 is 1, then we will go through this branch, and then again see if we have a branch leading to 0 on the 2nd bit, again we find it, then for the last time we are looking for a branch leading to 0 on the 3rd bit, but we do not find this, so we go down through another branch, which gives us Z = 001 . Thus, the maximum of W ^ Z will be equal to 7 ^ 1 = 6 . Now the difficulty of finding Z will be the maximum height of Trie , which will be log (MAX) .

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

Answer 2

With three nested loops:

 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; 

Answer 3

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

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

The complexity still remains n (n-1) (n-2) / 6 ===> O (N ^ 3).

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