Trie Interview Problem

#1

Do we need to make two trie in this 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

I am assuming you read the editorial.

Just mantain leftbest[] which is max xor subarray u can find in 0 to i
And rightbest which is max xor sub array u can find in i to n

And then just find max(leftbest[i]+ rightbest[i]);

This is variation of question
Maximum xor subarray
refer this blog to get a hint on the question https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/

#3

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.