Reduzca la array binaria reemplazando ambos pares 0 o 1 con 0 y 10 o 01 par con 1

Dada una array binaria arr[] de tamaño N , la tarea es encontrar el último número que queda en la array después de realizar un conjunto de operaciones. En cada operación, seleccione dos números cualesquiera y realice lo siguiente:

• Si ambos números son iguales, elimínelos de la array e inserte un 0 .
• Si ambos números son diferentes, elimínelos e inserte un 1 .

Ejemplo:

Entrada: arr[]={0, 0, 1}
Salida: 1
Explicación: Hay dos posibles secuencias de operaciones de la siguiente manera:

• arr[] = {0, 0, 1}, borre (0, 1) e inserte 0 => arr[] = {0, 0}, borre (0, 0) e inserte 1=> arr[] = {1 }.
• arr[] = {0, 0, 1}, borre (0, 0) e inserte 0 => arr[] = {0, 1}, borre (0, 1) e inserte 1=> arr[] = {1 }.

Por lo tanto, el elemento restante es 1.

Entrada: arr[]={1, 0, 0, 0, 1}
Salida: 0

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• 2 números iguales están siendo reemplazados por un 0.
• 2 números diferentes están siendo reemplazados por un 1.

Ahora, la creación de una tabla para cada resultado:

Tras una cuidadosa observación de la tabla anterior, se puede notar que la tabla representa la operación XOR bit a bit . Por lo tanto, el entero restante será igual al XOR bit a bit de los elementos de array dados que se pueden simplificar aún más como si la frecuencia de 1 fuera par, el resultado es 0 , de lo contrario, es 1 .

A continuación se muestra la implementación del enfoque anterior.

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find last remaining
// integer in the given array
int lastNumber(vector<int>& arr)
{
 
    // Variable to store the
    // frequency of 1
    int one = 0;
 
    // Loop to iterate the
    // given array
    for (int x : arr) {
        if (x == 1) {
            one += 1;
        }
    }
 
    // If frequency of 1 is even
    if (one % 2 == 0)
        return 0;
 
    // If frequency of 1 is odd
    return 1;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 0, 0, 0, 1 };
    cout << lastNumber(arr);
}

// Java program of the above approach
import java.util.ArrayList;
class GFG {
 
  // Function to find last remaining
  // integer in the given array
  static Integer lastNumber(ArrayList<Integer> arr)
  {
 
    // Variable to store the
    // frequency of 1
    int one = 0;
 
    // Loop to iterate the
    // given array
    for (int x : arr) {
      if (x == 1) {
        one += 1;
      }
    }
 
    // If frequency of 1 is even
    if (one % 2 == 0)
      return 0;
 
    // If frequency of 1 is odd
    return 1;
  }
 
  // Driver Code
  public static void main(String args[]) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    arr.add(1);
    arr.add(0);
    arr.add(0);
    arr.add(0);
    arr.add(1);
 
    System.out.println(lastNumber(arr));
  }
}
 
// This code is contributed by gfgking

# python program of the above approach
 
# Function to find last remaining
# integer in the given array
def lastNumber(arr):
 
    # Variable to store the
    # frequency of 1
    one = 0
 
    # Loop to iterate the
    # given array
    for x in arr:
        if (x == 1):
            one += 1
 
    # If frequency of 1 is even
    if (one % 2 == 0):
        return 0
 
    # If frequency of 1 is odd
    return 1
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 0, 0, 0, 1]
    print(lastNumber(arr))
 
# This code is contributed by rakeshsahni

// C# program of the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find last remaining
// integer in the given array
static int lastNumber(List<int> arr)
{
     
    // Variable to store the
    // frequency of 1
    int one = 0;
 
    // Loop to iterate the
    // given array
    foreach(int x in arr)
    {
        if (x == 1)
        {
            one += 1;
        }
    }
 
    // If frequency of 1 is even
    if (one % 2 == 0)
        return 0;
 
    // If frequency of 1 is odd
    return 1;
}
 
// Driver Code
public static void Main()
{
    List<int> arr = new List<int>(){ 1, 0, 0, 0, 1 };
     
    Console.WriteLine(lastNumber(arr));
}
}
 
// This code is contributed by ukasp

<script>
      // JavaScript code for the above approach
 
 
      // Function to find last remaining
      // integer in the given array
      function lastNumber(arr) {
 
          // Variable to store the
          // frequency of 1
          let one = 0;
 
          // Loop to iterate the
          // given array
          for (let x of arr) {
              if (x == 1) {
                  one += 1;
              }
          }
 
          // If frequency of 1 is even
          if (one % 2 == 0)
              return 0;
 
          // If frequency of 1 is odd
          return 1;
      }
 
      // Driver Code
 
      let arr = [1, 0, 0, 0, 1];
      document.write(lastNumber(arr));
 
// This code is contributed by Potta Lokesh
  </script>

0

Complejidad temporal: O(N)
Espacio auxiliar: O(1)