Minimum number of operations to make XOR of array equal to zero

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:

1. Select the element on which you will perform the operations. Note that all the operations must be performed only on the selected element.
2. 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

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

Explanation of solution

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

We can solve this problem by two approaches:

1. 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²).
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
2. Optimized solution: This solution is an optimzed veersion of the solution above. In this solution we will utilise three important facts about XOR:
   1. It is associative.
   2. XOR of an element with itself is zero.
   3. XOR of a number with zero is the number itself.
   The above behavior implies an important behavior of XOR that is if M = a^b ( 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.

Solution

• C++
• Java
• Python

#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;
}

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));
    }
}
   

#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 :)