Any one please explain how gausssian elimination in order to find the maximum xor subset over an array?</pre? [https://www.hackerearth.com/notes/gaussian-elimination/]I read the tutorial here but i was not unable to understand how GE works here. : https://www.hackerearth.com/notes/gaussian-elimination/
One does not need to understand gaussian elimination to solve the problem. If we had 1 element say n for each i where 2^^i+1>n>2^^i we just had to xor each element and check if it is greater than max. I am not going in detail as u should have understood it if u had researched a lot on it. Now the question arises how to convert the original array to such array where there is only one element for each i. This is the part which I dont think there’s a clear explanation on the net.
Take out all possible xor subsets of (7,5,6) and now take out all possible xor subsets of (2,5,6) .They come out to be same. Guess why we replaced 7 by 7 xor 5. Now take out xor subsets of (2,5,(5^6)). Even this comes out to be same.Now guess what, in the list which had 3 numbers of i==2 now we have only 1. Now I guess you should be smart enough to figure out the soultion