here it is given that the max xor produced in the range 6-8 is 14 by doing xor of 6 & 8. if i do xor of 7 & 8, i’m getting 15 as the ans. would u make me understand this?
About the example test case
You have to use elements present in the array only.
In this question for the array a , you have to find ,the maximum value of (arr[a] ^ arr[a + 1] ^ arr[a + 2] ……… arr[b]) + (arr[c] ^ arr[c + 1] ^ arr[c + 2] ……… arr[d]) where 1 <= a <= b <= c <= d <= N
i.e you have to find the maximum value of sum of XOR of two non overlapping subarrays
for eg :-
4
1 2 6 8
some combinations can be :-
(1^2)+(8^8) = 3 + 0 = 0=3
(1^1)+(2^2) =0
.
.
.
(1^2)+(6^8) = 3 +14 =17
(1^2^6) + (8^8) = 9 + 0=9
(1^1)+(2^6^8) = 0 + 12 =12
since max value is 17 for this case so the answer should be 17
but in the question, the range is given as 1-2 and 6-8 , then how have u included (1^2^6)+(8^8)?
No that hyphen is and actually so 6 and 8 are the elements used
so, how do i approach this prob?
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
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.