Help me out here!

#1

Not able to understand the question properly, please help me out

Not able to understand the question
#2

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

1 Like
#3

Iss question ko trie mein kaise visualize krr skte hai…Any hint bhaii

#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.

this might be complicated for you
refer this blog to get a hint on the question