Given a binary array of 0’s and 1’s, the task is to find the number of ways to erase exactly one element from this array to make XOR zero.
Examples:
Input: arr = {1, 1, 1, 1, 1 }
Output: 5
You can erase any of the given 5 1's,
it will make the XOR of the rest equal to zero.
Input: arr = {1, 0, 0, 1, 0 }
Output: 3
Since the XOR of array is already 0,
You can erase any of the given 3 0's
so that the XOR remains unaffected.
Approach: Since we know that, to make XOR of binary elements be 0, the number of 1’s should be even. Hence this problem can be broken into 4 cases:
- When the number of 1’s is even and the number of 0’s is also even in the given array: In this scenario, the XOR of the array is already 0. Hence to keep the XOR unaffected, we can remove only the 0’s. Hence the number of ways to erase exactly one element from this array to make XOR zero is the number of 0’s in this array.
- When the number of 1’s is even and the number of 0’s is odd in the given array: In this scenario, the XOR of the array is already 0. Hence to keep the XOR unaffected, we can remove only the 0’s. Hence the number of ways to erase exactly one element from this array to make XOR zero is the number of 0’s in this array.
- When the number of 1’s is odd and the number of 0’s is even in the given array: In this scenario, the XOR of the array is 1. Hence to make the XOR 0, we can remove any of the 1’s. Hence the number of ways to erase exactly one element from this array to make XOR zero is the number of 1’s in this array.
- When the number of 1’s is odd and the number of 0’s is also odd in the given array: In this scenario, the XOR of the array is 1. Hence to make the XOR 0, we can remove any of the 1’s. Hence the number of ways to erase exactly one element from this array to make XOR zero is the number of 1’s in this array.
Below is the implementation of the above approach:
C++
// C++ program to find the number of ways// to erase exactly one element// from this array to make XOR zero#include <bits/stdc++.h>using namespace std;// Function to find the number of waysint no_of_ways(int a[], int n){ int count_0 = 0, count_1 = 0; // Calculate the number of 1's and 0's for (int i = 0; i < n; i++) { if (a[i] == 0) count_0++; else count_1++; } // Considering the 4 cases if (count_1 % 2 == 0) return count_0; else return count_1;}// Driver codeint main(){ int n = 4; int a1[4] = { 1, 1, 0, 0 }; cout << no_of_ways(a1, n) << endl; n = 5; int a2[5] = { 1, 1, 1, 0, 0 }; cout << no_of_ways(a2, n) << endl; n = 5; int a3[5] = { 1, 1, 0, 0, 0 }; cout << no_of_ways(a3, n) << endl; n = 6; int a4[6] = { 1, 1, 1, 0, 0, 0 }; cout << no_of_ways(a4, n) << endl; return 0;} |
Java
// Java program to find the number of ways // to erase exactly one element // from this array to make XOR zero class GFG{ // Function to find the number of ways static int no_of_ways(int a[], int n) { int count_0 = 0, count_1 = 0; // Calculate the number of 1's and 0's for (int i = 0; i < n; i++) { if (a[i] == 0) count_0++; else count_1++; } // Considering the 4 cases if (count_1 % 2 == 0) return count_0; else return count_1; } // Driver code public static void main (String[] args) { int n = 4; int a1[] = { 1, 1, 0, 0 }; System.out.println(no_of_ways(a1, n)); n = 5; int a2[] = { 1, 1, 1, 0, 0 }; System.out.println(no_of_ways(a2, n)); n = 5; int a3[] = { 1, 1, 0, 0, 0 }; System.out.println(no_of_ways(a3, n)); n = 6; int a4[] = { 1, 1, 1, 0, 0, 0 }; System.out.println(no_of_ways(a4, n)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 program to find the number of ways # to erase exactly one element # from this array to make XOR zero # Function to find the number of ways def no_of_ways(a, n): count_0 = 0 count_1 = 0 # Calculate the number of 1's and 0's for i in range(0, n): if (a[i] == 0): count_0 += 1 else: count_1 += 1 # Considering the 4 cases if (count_1 % 2 == 0): return count_0 else: return count_1 # Driver code if __name__ == '__main__': n = 4 a1 = [ 1, 1, 0, 0 ] print(no_of_ways(a1, n)) n = 5 a2 = [ 1, 1, 1, 0, 0 ] print(no_of_ways(a2, n)) n = 5 a3 = [ 1, 1, 0, 0, 0 ] print(no_of_ways(a3, n)) n = 6 a4 = [ 1, 1, 1, 0, 0, 0 ] print(no_of_ways(a4, n)) # This code is contributed by ashutosh450 |
C#
// C# program to find the number of ways // to erase exactly one element // from this array to make XOR zero using System;class GFG{ // Function to find the number of ways static int no_of_ways(int []a, int n) { int count_0 = 0, count_1 = 0; // Calculate the number of 1's and 0's for (int i = 0; i < n; i++) { if (a[i] == 0) count_0++; else count_1++; } // Considering the 4 cases if (count_1 % 2 == 0) return count_0; else return count_1; } // Driver code public static void Main () { int n = 4; int [] a1 = { 1, 1, 0, 0 }; Console.WriteLine(no_of_ways(a1, n)); n = 5; int [] a2 = { 1, 1, 1, 0, 0 }; Console.WriteLine(no_of_ways(a2, n)); n = 5; int [] a3 = { 1, 1, 0, 0, 0 }; Console.WriteLine(no_of_ways(a3, n)); n = 6; int [] a4 = { 1, 1, 1, 0, 0, 0 }; Console.WriteLine(no_of_ways(a4, n)); } }// This code is contributed by Mohit kumar |
Javascript
<script>// Javascript program to find the number of ways// to erase exactly one element// from this array to make XOR zero// Function to find the number of waysfunction no_of_ways(a, n){ let count_0 = 0, count_1 = 0; // Calculate the number of 1's and 0's for (let i = 0; i < n; i++) { if (a[i] == 0) count_0++; else count_1++; } // Considering the 4 cases if (count_1 % 2 == 0) return count_0; else return count_1;}// Driver code let n = 4; let a1 = [ 1, 1, 0, 0 ]; document.write(no_of_ways(a1, n) + "<br>"); n = 5; let a2 = [ 1, 1, 1, 0, 0 ]; document.write(no_of_ways(a2, n) + "<br>"); n = 5; let a3 = [ 1, 1, 0, 0, 0 ]; document.write(no_of_ways(a3, n) + "<br>"); n = 6; let a4 = [ 1, 1, 1, 0, 0, 0 ]; document.write(no_of_ways(a4, n) + "<br>");</script> |
Output:
2 3 3 3
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!