Given an array of elements, how do we find the XOR of each sub-array and XOR of those results?

For example let us consider the array [1, 2, 3], all possible sub-arrays are

XOR[1] = 1

XOR[1, 2] = 1 ^ 2 = 3

XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0

XOR[2] = 2

XOR[2, 3] = 2 ^ 3 = 1

XOR[3] = 3

And the result XOR[1, 3, 0, 2, 1, 3] = 2.

From the above example, you can see that an array of 3 elements has 6 sub-arrays. Similarly you can verify the count by listing the sub-arrays for N= 4 and N= 5. In general, for an array of N elements there will be N*(N+1)/2 sub-arrays. We have to calculate the XOR of each of these sub arrays. So an outline of algorithm can be as follows.

for i in range(1,N)

for j in range(i,N)

for k in range(i,j)

x = XOR(x,A[k])

This is clearly not en efficient solution and take O(n

Observe how many times, each element appear in all the sub arrays. In the above example

1 - 3 times

2 - 4 times

3 - 3 times

Consider

We also know that if an element is XOR'ed with itself even number of times, it is zeroed out. and if it is odd number of times, it remains the same. For example

V ^ V ^ V ^ V = 0

V ^ V ^ V = V

Consider the two cases when the number of elements N is Even or Odd

N= 2,

A[0] - 2 times

A[1] - 2 times

N = 4,

A[0] - 4 times

A[1] - 6 times

A[2] - 6 times

A[3] - 4 times

This is because either (N-i) or (i+1) is always even for all values of i.

Hence, for an array of even length, the XOR of all sub-array becomes

The following C++ program implements the above approach. The time complexity of this algorithm is O(n).

For example let us consider the array [1, 2, 3], all possible sub-arrays are

XOR[1] = 1

XOR[1, 2] = 1 ^ 2 = 3

XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0

XOR[2] = 2

XOR[2, 3] = 2 ^ 3 = 1

XOR[3] = 3

And the result XOR[1, 3, 0, 2, 1, 3] = 2.

__Brute force solution:__From the above example, you can see that an array of 3 elements has 6 sub-arrays. Similarly you can verify the count by listing the sub-arrays for N= 4 and N= 5. In general, for an array of N elements there will be N*(N+1)/2 sub-arrays. We have to calculate the XOR of each of these sub arrays. So an outline of algorithm can be as follows.

for i in range(1,N)

for j in range(i,N)

for k in range(i,j)

x = XOR(x,A[k])

This is clearly not en efficient solution and take O(n

^{3}) time. We can also use dynamic programming to pre-calculate the XOR values so that time can be reduced to O(n^{2}). But is there any better method?__Efficient Solution:__Observe how many times, each element appear in all the sub arrays. In the above example

1 - 3 times

2 - 4 times

3 - 3 times

Consider

__, in general A[i] appears (N-i)*(i+1) times.__*0-index*We also know that if an element is XOR'ed with itself even number of times, it is zeroed out. and if it is odd number of times, it remains the same. For example

V ^ V ^ V ^ V = 0

V ^ V ^ V = V

Consider the two cases when the number of elements N is Even or Odd

*N is even*, each element appear even number of times:N= 2,

A[0] - 2 times

A[1] - 2 times

N = 4,

A[0] - 4 times

A[1] - 6 times

A[2] - 6 times

A[3] - 4 times

This is because either (N-i) or (i+1) is always even for all values of i.

Hence, for an array of even length, the XOR of all sub-array becomes

*Zero*.*N is odd*, the elements at even index will only prevail in the final result.The following C++ program implements the above approach. The time complexity of this algorithm is O(n).