Find the subarray whose xor is maximum with given X [XORX , SPOJ]

Question : “https://www.spoj.com/problems/XORX/

Can anyone help me in this question , I don’t know how to solve tried to figure out but no sense , please help @galencolin @everule1 @udayan14 @aryan12 @carre

first XOR all numbers with x and then find the maxium subarray XOR as explained here

[EDIT] nop, I simplified it and that’s not right, let me think it a little bit

Bro this is different I think , I know it is solved by Trie.

UPD : Yeah please think , and explain to me -

I found one solution if u explain from this I will be very thankful -

  1. https://github.com/tr0j4n034/SPOJ/blob/master/XORX.cpp

before reading that I think that somethiing can be done mantaining 2 tries, one of them to get the odd-lenght subarrays and other to even-lenght

How ? elaborate more.

they both do almost the same, in the get function of the tree they xor the current bit with the bit of the value of X, and that’s it, it’s fine and simple

Not able to understand that guy code , that’s why I ask here .

Have you read the solution I linked? It’s almost the same, the only difference is that when you query the tree you XOR with x value also

The query should do the following for each bit
if current_prefix_bit ^ X_bit ==1 got to 0 branch of tree
else go to 1 branch of tree

Yeah I know that solution u linked (gfg) , in that we find the max xor of subarray ending at i'th index and find maximum value from each i , but how this is applied here I don’t know .

One more : “https://github.com/t3nsor/SPOJ/pull/7/commits/248246748cc109282d908d5cf81f14e77063960d

Here he just find the answer by passing the value (pre^x) into query and find max val [ just like your gfg link ] , but after that he use this loop why -?

for(ll i=id;i>=0;i--)
    {
    	xo=(xo^arr[i]);
    	if((xo^m)==ans)
    	{
    		return xo;
    	}

the difference here is that he queries before inserting current prefix so at the end he needs to xor with the current prefix