XOR of all sub arrays

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.

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(n3) time. We can also use dynamic programming to pre-calculate the XOR values so that time can be reduced to O(n2). 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 0-index, in general A[i] appears (N-i)*(i+1) times. 

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).

Leave a Reply

Your email address will not be published. Required fields are marked *