Get this book -> Problems on Array: For Interviews and Competitive Programming

You are given an array of n non-negative integers.** Your task is to find the minimum number of operations to make XOR of array equal to zero by performing the operations which are defined as follows:**

- Select the element on which you will perform the operations. Note that all the operations must be performed only on the selected element.
- The operation that can be performed are increment and decrement by one.

## Examples

```
Input:
No. of elements in array = 3
Elements = 2 4 7
Output:
1
```

**Explanation: We will decrement 7 to 6 and then the XOR of all the elements is zero.**

```
Input:
No. of elements in array = 4
Elements = 5 5 4 4
Output:
0
```

**Explanation: XOR of an element with itself is zero.**

## Explanation of solution

Before discussing the various approaches to the problem let us briefly review XOR.**XOR**(

*also known as exclusive-or*) of two one bit number is defined by the following table:

A |
B |
A ^ B |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

#### XOR of two many bit numbers is simply the XOR of the corresponding individual bits.

**Example: The XOR of 5 (101 in binary) and 6 (110 in binary) will be 011 in binary or 3 in decimal.**

**Property of XOR: XOR of two numbers can be zero only when both the numbers are equal.**

We can solve this problem by two approaches:

**Brute force approach:**Let the selected element be the i^{th}element. Now let us find the XOR of the all the elements excluding the ith element (*n operations*). Now, if the obtained XOR is equal to the i^{th}element, then we don't need to perform any operation as XOR of whole array is already zero; otherwise the no. of operations (*or cost*) required on the i^{th}element will be equal to the absolute difference of obtained XOR and array[i]. Also, we need to calculate the calculate the cost for each element and the minimum of these will be the answer. Hence, the complexity of the solution will be**Θ(n**.^{2})**Optimized solution:**This solution is an optimzed veersion of the solution above. In this solution we will utilise three important facts about XOR:**It is associative.****XOR of an element with itself is zero.****XOR of a number with zero is the number itself.**

*a and b are numbers*) then M^b will be equal to a.

Now with this property in hand, we will make the process of finding the XOR of all elements excluding the i^{th}element O(1). First, we will find XOR of all the elements of the array and store it in a variable (*lets say A*). Then to find the XOR of all the elements excluding the i^{th}element we will do XOR(A, array[i]). Thus the cost for the i^{th}element will be**absolute(array[i]-XOR(A, array[i]))**. We will calculate the cost for each element of the array and the minimum of these costs will be the answer.

**EXAMPLE:**Let us find the answer when the

**elements of array are 2, 4 ,7 and 8.**Now we need to find the minimum number of changes to one element so that XOR of the array is zero.

Let us assume that selected number is 2. Then we must change 2 to become equal to 4 XOR 7 XOR 8 i.e. 11. Operations for 2 are equal to 9. Similarly, operations for 4, 7 and 8 are equal to 9, 7 and 7 respectively. Answer is equal to

**minimum(9,9,7,7)**i.e.

**7**

**EXAMPLE:**Let us find the answer when the array is:

Array |
|||
---|---|---|---|

2 |
4 |
7 |
8 |

**M. M = 2 XOR 4 XOR 7 XOR 8 i.e. M = 9.**

Let us assume that selected number is 2. Then we must change 2 to become equal to M XOR 2

**i.e. 11. So operations for 2 are equal to 9. Similarly, operations for 4, 7 and 8 are equal to 9, 7 and 7 respectively (We will run a loop over the array for this). Answer is equal to**

*(XOR of all numbers excluding two)***minimum(9,9,7,7)**i.e.

**7**.

In this way we have reduced the complexity from

**n**where n is the number of elements in the array.

^{2}to n## Solution

- C++
- Java
- Python

### C

```
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
```

//function definition
int minxor(int matrix[], int length){
int answer=INT_MAX,obtainedxor=0;
for(int i=0;i<length;++i){
obtainedxor^=matrix[i];
}

int cost;
for(int i=0;i<length;++i){
cost=abs((obtainedxor^matrix[i])-matrix[i]);
if(answer>cost){
answer=cost;
}
}

return answer;
}

int main(){
//input
int length;
cout<<"No. of elements in array = ";
cin>>length;
int matrix[length];
cout<<"Elements = ";
for(int i=0;i<length;++i){
cin>>matrix[i];
}

//output
cout<<minxor(matrix, length)<<"\n";
return 0;
}

### C++

```
import java.lang.*;
import java.util.*;
```

class OPENGENUS{
//function definition
static int minxor(int matrix[], int length){
int answer=Integer.MAX_VALUE,obtainedxor=0;
for(int i=0;i<length;++i){
obtainedxor^=matrix[i];
}

int cost;
for(int i=0;i<length;++i){
cost=Math.abs((obtainedxor^matrix[i])-matrix[i]);
if(answer>cost){
answer=cost;
}
}

return answer;
}

public static void main(String [] args){
//input
int length;
Scanner sc = new Scanner(System.in);
System.out.print("No. of elements in array = ");
length = sc.nextInt();
int matrix[] = new int[length];
System.out.print("Elements = ");
for(int i=0;i<length;++i){
matrix[i]=sc.nextInt();
}

//output
System.out.println(minxor(matrix,length));
}
}

### Python

```
#function definition
def minxor(matrix,length):
```

obtainedxor = 0
answer = 9999999999
for i in range(length):
obtainedxor^=matrix[i]

for i in range(length):
cost = abs((obtainedxor^matrix[i])-matrix[i])
if answer>cost:
answer=cost

return answer

#input
length = int(input("No of elements in array = "))
matrix = []

print("Elements = ", end="")
for i in range(length):
matrix.append(int(input()))

#output
print(minxor(matrix,length))

## Time Complexity

- Worst case time complexity:
`O(N)`

- Average case time complexity:
`Î˜(N)`

- Best case time complexity:
`Î©(N)`

- Auxiliary space:
`O(1)`

- Space complexity:
`Θ(N)`

Feel free to share your approach in the discussion thread below. Happy Coding :)