Dada una array binaria de 0 y 1, la tarea es encontrar el número de formas de borrar exactamente un elemento de esta array para hacer que XOR sea cero.
Ejemplos:
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.
Enfoque: Ya que sabemos que, para hacer que XOR de elementos binarios sea 0, el número de 1 debe ser par. Por lo tanto, este problema se puede dividir en 4 casos:
- Cuando el número de 1 es par y el número de 0 también es par en la array dada: En este escenario, el XOR de la array ya es 0. Por lo tanto, para que el XOR no se vea afectado, podemos eliminar solo los 0. Por lo tanto, la cantidad de formas de borrar exactamente un elemento de esta array para hacer que XOR sea cero es la cantidad de 0 en esta array.
- Cuando el número de 1 es par y el número de 0 es impar en la array dada: En este escenario, el XOR de la array ya es 0. Por lo tanto, para que el XOR no se vea afectado, podemos eliminar solo los 0. Por lo tanto, la cantidad de formas de borrar exactamente un elemento de esta array para hacer que XOR sea cero es la cantidad de 0 en esta array.
- Cuando el número de 1 es impar y el número de 0 es par en la array dada: En este escenario, el XOR de la array es 1. Por lo tanto, para hacer que el XOR sea 0, podemos eliminar cualquiera de los 1. Por lo tanto, la cantidad de formas de borrar exactamente un elemento de esta array para hacer que XOR sea cero es la cantidad de 1 en esta array.
- Cuando el número de 1 es impar y el número de 0 también es impar en la array dada: En este escenario, el XOR de la array es 1. Por lo tanto, para hacer que el XOR sea 0, podemos eliminar cualquiera de los 1. Por lo tanto, la cantidad de formas de borrar exactamente un elemento de esta array para hacer que XOR sea cero es la cantidad de 1 en esta array.
A continuación se muestra la implementación del enfoque anterior:
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 ways
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
int 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 ways
function 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>
Producción:
2 3 3 3
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)