xor sum ACM Amritapuri 2009

general
1

problem

how to find maximum xor of contiguous sub-sequence of array

1 Like
2

It’s a disguised Maximum Subarray Problem. Just replace the sum with a xor operation in the Kadane loop, and that’s it. :slight_smile: Hope it helps.

3

That’s not true. Xor will never be negative, so you will just receive maximum xor on prefix.

4 Likes
4

Let f(L,R) = xor sum of subarray a[L…R], then f(L,R) = f(1,R) xor f(1,L-1).

Now, suppose, that we have a data structure that allows us to perform this two operations: insert some integer into this structure and for given integer X find an Y, with maximal X xor Y value.

Then we can solve the task like this:

Answer = 0;
XorOnPrefix = 0;
Structure.insert(0);
for i = 1 to n
    XorOnPrefix = XorOnPrefix xor a_i;
    Structure.insert(XorOnPrefix);
    Answer = max(Answer, Structure.query(XorOnPrefix) xor XorOnPrefix);
return Answer;

Now, about the data structure. It can be implemented as trie (prefix tree), if we consider integers as binary strings of length logA = 32. Then insertion can be done in O(logA) time. And answering the queries can be done like this, also in O(logA) time:

Structure.query(x):
v = Root of the trie;
y = 0;
for i = 31 to 0
    b = i-th bit in binary representation of x;
    if ( v.child(b xor 1) = -1 )
        v = v.child(b);
        y = y + (2^i) * b;
    else
        v = v.child(b xor 1);
        y = y + (2^i) * (b xor 1);
return y;
17 Likes
5

Structure.query(XorOnPrefix) xor XorOnPrefix

why we need to xor with XorOnPrefix again?Structure.query(XorOnPrefix) is already giving maximum, is it not?

6

@dragonstone : Let XorOnPrefix be x, then Structure.query(XorOnPrefix) returns y such that x^y is maximum among all y that belong to the Query data structure.

7

I tried the same logic but it’s giving wrong answer again and again.

8

Maximum Subarray Problem Cant be applied in this problem because it will not find always maximum XOR i.e let say we have an array {6,8,7}
according to you(cyberax) 6^8=14 ans = max(14^7,7) =14 right ??
but you can see that 7^8=15 which is correct, radix trie (or prefix trie ) is the right solution for this problem.

9

why can’t we use segment tree to find the maximum subarray xor?

10

Because it’s not true that the xor of two maximum sub segments will yield another greater sub segment.

11