Maximum xor among all subsets of an array

Question

I have to find maximum value of exclusive xor among the elements of subsets of an array. I have to check every subset of the array and the subset which will yield maximum xor will be the answer.

For exapmle- let F(S) denote the fuction which takes xor over all elements of subset S of array P={1,2,3,4}

F({1,2}) = 3
F({1,3}) = 2
F({1,2,3}) = 0  
F({1,4}) = 5
F({2,3}) = 1  
F({2,4}) = 6  
F({3,4}) = 7  
F({2,3,4}) = 5  
F({1,2,3,4}) = 4`  

Maximum of them is 7. Hence the answer is 7.(There are other subsets but they are not worth considering). If you are about to tell me about Gaussian Elimination method, I've read that somewhere on MSE but it was not at all clear to me. If gauss elimination is the only answer than please elaborate that to me or is there some method/algorithm I don't know of?

Answer 1

Gaussian Elimination is what you need.

For example : 3 numbers {9, 8, 5}

First sort them in decreasing order and convert them into binary :

9 : 1001
8 : 1000
5 : 0101

Observe the 1st number. Highest bit is 4.
Now check 4th bit of the 1st number (9). As it is 1, xor the number with the rest of the numbers where 4th bit is 1.

9 : 1001
1 : 0001 > changed
5 : 0101

Now check 3rd bit of 2nd number (1). As it is 0, check rest of the below numbers where 3rd bit is 1.
Number 5 has 1 in 3rd bit. Swap them :

9 : 1001
5 : 0101 > swapped
1 : 0001 >

Now xor 5 with the rest of the numbers where 3rd bit is 1. Here none exists. So there will be no change.

Now check 2nd bit of 3rd number (1). As it is 0 and there is no other number below where 2nd bit is 1, so there will be no change.

Now check 1st bit of 3rd number (1). As it is 1, change the rest of the numbers where 1st bit is 1.

8 : 1000 > changed
4 : 0100 > changed
1 : 0001

No more bit left to consider :)

Now xor the whole remaining array {8 ^ 4 ^ 1} = 13

So 13 is the solution :)

That's pretty much how you solve the problem using Gaussian Elimination :)

Here is my C++ implementation :

#include <bits/stdc++.h>
using namespace std;

typedef long long int           ll;
typedef unsigned long long int  ull;

ull check_bit(ull N,int POS){return (N & (1ULL<<POS));}

vector<ull>v;
ull gaussian_elimination()
{
    int n=v.size();
    int ind=0;  // Array index
    for(int bit=log2(v[0]);bit>=0;bit--)
    {
        int x=ind;
        while(x<n&&check_bit(v[x],bit)==0)
          x++;
        if(x==n)
          continue; // skip if there is no number below ind where current bit is 1
        swap(v[ind],v[x]);
        for(int j=0;j<n;j++)
        {
            if(j!=ind&&check_bit(v[j],bit))
                v[j]^=v[ind];
        }
        ind++;
    }
    ull ans=v[0];
    for(int i=1;i<n;i++)
      ans=max(ans,ans^v[i]);
    return ans;
}
int main()
{
    int i,j,k,l,m,n,t,kase=1;
    scanf("%d",&n);
    ull x;
    for(i=0;i<n;i++)
    {
        cin>>x;
        v.push_back(x);
    }
    sort(v.rbegin(),v.rend());
    cout<<gaussian_elimination()<<"\n";
return 0;
}

Answer 2

I guess that you're referring to this question.

Gaussian Elimination is the algorithm description that I would expect from the math site. This is what the algorithm looks like in Python.

def max_xor(iterable):
    array = list(iterable)  # make it a list so that we can iterate it twice
    if not array:  # special case the empty array to avoid an empty max
        return 0
    x = 0
    while True:
        y = max(array)
        if y == 0:
            return x
        # y has the leading 1 in the array
        x = max(x, x ^ y)
        # eliminate
        array = [min(z, z ^ y) for z in array]