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

  1. Brute force approach: Let the selected element be the ith 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 ith 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 ith 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 Θ(n2).
  2. 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
  3. 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 ith 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 ith element we will do XOR(A, array[i]). Thus the cost for the ith 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 array is:
Array
2 4 7 8
Now we need to find the minimum number of changes to one element so that XOR of the array is zero. Let us find the XOR of the whole array and store it in a variable 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 (XOR of all numbers excluding two) 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 minimum(9,9,7,7) i.e. 7.
In this way we have reduced the complexity from n2 to n where n is the number of elements in the array.

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)
where N is the number of elements

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