Https://ide.codingblocks.com/s/164472

#1

please tell whats wrong with my approach

#2

@sarthaksingh
As you can clearly see , your code fails for the sample testcase. The reason being your code takes the collective XOR of all elements before the index i and computes the result based on that. Moreover its not neccessary to take XOR of all elements after index i till index N as well. The beginning point of first is not necessarily the 0th index and last index of second part doesn’t necessarily have to be the last index. Your approach is wrong. If you were to go for a brute force approach , you would have to use four loops atleast which is very likely to give a TLE. Hence this problem is given in the Trie section so you can construct a proper optimum solution using the trie data structure.
Let me give you some hints to solve this problem using the Trie data structure.4 :
We can construct two arrays lbest and rbest for the left hand side of the expression and for the right hand side of the expression. To calculate lbest[i] we will iterate m from i to i such that (arr[m] ^ arr[m+1] ^ arr[m+2] … arr[i]) is maximised. Then lbest[i] = Max(lbest[i-1], val). Similar can be done for rbest. Now we will calculate val. Let C[i] = (arr[1] ^ arr[2] ^ arr[3] … arr[i]). For some j <= i, C[j-1] ^ C[i] = ( arr[j] ^ arr[j+1] ^ arr[j+2] … arr[i] ). ​We can now say that lbest[i] = max(lbest[i−1],val) where val = maximum of (C[j−1]C[i]) for j = 1 to i. Now using Tries we can easily calculate ‘val’ in (log arr(max)). We can store the bits of each number in the nodes of trie and iterate through the trie such that we can get the maximum xor possible.

#3

please can you post the code for reference

#4

@sarthaksingh
I cannot share the working code as that wouldn’t be right. I suggest you try it out once and I can suggest some changes with that.

#5

i tried to understand the approach that was suggested but wasn’t able to figure out

#6

@sarthaksingh
Kindly refer to this response by @prashuk156. I believe this should solve your doubt.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

what is m in hint a[m]+a[m+1]+…a[i]?.