# Game of XOR

In this article, we are going to see how to solve a problem on bitwise XOR? The problem has been featured in Amazon interview.
Submitted by Radib Kar, on March 29, 2019

Problem statement:

You are given an array A[] 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
```

Solution:

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:

```    For input array:
1, 2, 3, 4
Sub arrays are:
{1}
{2}
{3}
{4}
{1, 2}
{2, 3}
{3, 4}
{1, 2, 3}
{2, 3, 4}
{1, 2, 3, 4}

This is all possible sub arrays
A prompt observation leads to the fact that every element
actually occurred even number of times while XORing all values
1^2^3^4^(1^2)^(2^3)^(3^4)^(1^2^3)^(2^3^4)^(1^2^3^4)

1 has appeared 4 times
2 has appeared 6 times
3 has appeared 6 times
4 has appeared 4 times
So the final result is actually 0

Now take any even length array
You will find all elements appearing even no of times
if you expand the XORing sequence like the previous one.
So,
For even length array the output will be always 0,
no matter what the elements are.

Let's quickly revise an example
The array be:
1, 2, 3, 4, 5
So,
Subarrays are:
{1}
{2}
{3}
{4}
{1, 2}
{2, 3}
{3, 4}
{4, 5}
{1, 2, 3}
{2, 3, 4}
{3, 4, 5}
{1, 2, 3, 4}
{2, 3, 4, 5}
{1, 2, 3, 4, 5}
So the expanded result sequence would be:

1^2^3^4^5^(1^2)^(2^3)^(3^4)^(4^5)^(1^2^3) ^
(2^3^4) ^ (3^4^5) ^ (1^2^3^4) ^(2^3^4^5) ^ (1^2^3 ^4^5)

So, 1 appears 5 times //resulting 1
2 appears 8 times //resulting 0
3 appears 9 times //resulting 3
4 appears 8 times //resulting 0
5 appears 5 times //resulting 5
Output will be : 1^3^5
```

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-

1. Even length array: output 0
2. Odd length array: XORing all even-indexed elements

No need to compute all the sub arrays at all!!

C++ implementation:

```#include <bits/stdc++.h>
using namespace std;

int gameOfXor(vector<int> a,int n){
if(a.size()%2==0) //for even length array
return 0;

int sum=a;
// for odd length array
for(int it=2;it<a.size();it=it+2)
sum=sum^a[it];
return sum;
}

int main(){
int n,item;

cout<<"Enter number of elements\n";
scanf("%d",&n);

vector<int> a;

cout<<"Enter array elements\n";
for(int j=0;j<n;j++){
scanf("%d",&item);
a.push_back(item);
}

cout<<"Output is:\n";
cout<<gameOfXor(a,n)<<endl;

return 0;
}
```

Output

```First run:
Enter number of elements
4
Enter array elements
1 2 3 4
Output is:
0

Second run:
Enter number of elements
5
Enter array elements
1 2 3 4 5
Output is:
7
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates