Game of XOR
[] of size N. Now, we call the value of an array the bit-wise XOR of all elements it contains. For example, the value of the array [1,2, 3] = 1^2^3. Now, your task is to find the bit-wise XOR of the values of all sub-arrays of array A.
Example:
Input array:
1, 2, 3, 4
Subarrays and their XOR values
Subarray of length 1:
1 //value of the subarray: 1
2 //value of the subarray: 2
3 //value of the subarray: 3
4 //value of the subarray: 4
Subarray of length 2:
1, 2 //value of this subarray:1^2
2, 3 //value of this subarray:2^3
3, 4 //value of this subarray:3^4
Subarray of length 3
1, 2, 3 //value of this subarray:1^2^3
2, 3, 4 // value of this subarray:2^3^4
Subarray of length 4
1, 2, 3, 4 //value of this subarray:1^2^3^4
So
Bitwise XOR of all the values are
1^2^3^4^(1^2)^(2^3)^(3^4)^(1^2^3)^(2^3^4)^(1^2^3^4)
=0
One naïve approach can be of course to compute values ( XORing elements) for all subarrays. This is going to be real tedious as we need to find out all subarrays.
Effective approach can be the XOR nature. We know XORing an element twice results 0.
i^i=0
Let's revise our example:
Thus for an odd length array it's found that:
Result will be XORing of all even indexed elements (0-based indexing)
You can check the argue by doing few more examples your own.
So the entire problem actually reduced to a simple concept-
No need to compute all the sub arrays at all!!
C++ implementation:
Output