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