this can be easily solved in O(n^2) time but i am not able to think how to solve it in O(n) time please give any idea
How can i solve this question efficiently
Hello @Deepanshu_garg,
You can code the following approach:
-
Create an empty Trie. Every node of Trie is going to contain two children, for 0 and 1 value of the bit.
-
Initialize pre_xor = 0 and insert into the Trie.
-
Initialize result = minus infinite
-
Traverse the given array and do following for every array element arr[i].
a) pre_xor = pre_xor ^ arr[i]
pre_xor now contains xor of elements from
arr[0] to arr[i].
b) Query the maximum xor value ending with arr[i]
from Trie.
c) Update result if the value obtained in step
4.b) is more than the current value of the result.
To find maximum Xor value i.e. 4.b):
We can observe from the above algorithm that we build a Trie that contains XOR of all prefixes of the given array. To find the maximum XOR subarray ending with arr[i], there may be two cases.
i) The prefix itself has the maximum XOR value ending with arr[i]. For example, if i=2 in {8, 2, 1, 12}, then the maximum subarray xor ending with arr[2] is the whole prefix.
ii) We need to remove some prefix (ending at index from 0 to i-1). For example if i=3 in {8, 2, 1, 12}, then the maximum subarray xor ending with arr[3] starts with arr[1] and we need to remove arr[0].
To find the prefix to be removed, we find the entry in Trie that has maximum XOR value with the current prefix. If we do XOR of such previous prefix with current prefix, we get the maximum XOR value ending with arr[i].
If there is no prefix to be removed (case i), then we return 0 (that’s why we inserted 0 in Trie).
Hope, this would help.
Give a like, if you are satisfied.
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.