How to find the longest contiuous subarray whose XOR is 0

Question

For example, given {1,1,2,2}: the XOR of these subarrays are all 0: {1,1} , {2,2} , {1,1,2,2}. The length of the longest is 4.

Find the length of the longest subarray and return the beginning and end index of this subarray.

Answer 1

Compute a running XOR of the array, from 0 elements to all the elements. With your example:

initial 
segment         XOR
[]              0
[1]             1
[1, 1]          0
[1, 1, 2]       2
[1, 1, 2, 2]    0

Where two running XOR values are the same, the subarray between those two values will XOR to 0.

Create two maps, storing the first and last seen XOR value. Run through them, and find the pair with the largest difference.

In Python:

def continuous_xor(xs):
    xor = 0
    first_seen = {0: 0}
    last_seen = {0: 0}
    for i, x in enumerate(xs):
        xor = xor ^ x
        if xor not in first_seen:
            first_seen[xor] = i+1
        last_seen[xor] = i+1
    return max((last_seen[i]-first_seen[i], first_seen[i], last_seen[i]) for i in last_seen)

print continuous_xor([1, 1, 2, 2])
print continuous_xor([5, 1, 4, 3, 2, 4, 6])

The indices of the subarray are Python-style, with the start index being inclusive and the end index being exclusive.

This runs in O(n) time, where n is the size of the input array.