Compruebe si todos los elementos se pueden hacer de la misma paridad invirtiendo elementos adyacentes

Dada una array binaria. En una sola operación, puede elegir dos elementos adyacentes e invertir su paridad. La operación se puede realizar cualquier número de veces. Escriba un programa para verificar si todos los elementos de la array se pueden convertir en una sola paridad. 
Ejemplos: 
 

Entrada: a[] = {1, 0, 1, 1, 0, 1} 
Salida: Sí 
Invierta los elementos 2 y 3 para obtener {1, 1, 0, 1, 0, 1} 
Invierta los elementos 3 y 4 para obtener { 1, 1, 1, 0, 0, 1} 
Invierta los elementos 4 y 5 para obtener {1, 1, 1, 1, 1, 1}
Entrada: a[] = {1, 1, 1, 0, 0, 0 } 
Salida: No 
 

Enfoque: dado que solo se necesita voltear los elementos adyacentes, por lo tanto, el recuento de paridades dará la respuesta a la pregunta. Solo se invierte un número par de elementos a la vez, por lo que si el recuento de ambas paridades es impar, entonces no es posible hacer que todas las paridades sean iguales; de lo contrario, es posible.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if parity
// can be made same or not
bool flipsPossible(int a[], int n)
{
 
    int count_odd = 0, count_even = 0;
 
    // Iterate and count the parity
    for (int i = 0; i < n; i++) {
 
        // Odd
        if (a[i] & 1)
            count_odd++;
 
        // Even
        else
            count_even++;
    }
 
    // Condition check
    if (count_odd % 2 && count_even % 2)
        return false;
 
    else
        return true;
}
 
// Drivers code
int main()
{
    int a[] = { 1, 0, 1, 1, 0, 1 };
    int n = sizeof(a) / sizeof(a[0]);
 
    if (flipsPossible(a, n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
public class GFG
{
     
    // Function to check if parity
    // can be made same or not
    static boolean flipsPossible(int []a, int n)
    {
     
        int count_odd = 0, count_even = 0;
     
        // Iterate and count the parity
        for (int i = 0; i < n; i++)
        {
     
            // Odd
            if ((a[i] & 1) == 1)
                count_odd++;
     
            // Even
            else
                count_even++;
        }
     
        // Condition check
        if (count_odd % 2 == 1 && count_even % 2 == 1)
            return false;
     
        else
            return true;
    }
     
    // Drivers code
    public static void main (String[] args)
    {
        int []a = { 1, 0, 1, 1, 0, 1 };
        int n = a.length;
     
        if (flipsPossible(a, n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to check if parity
# can be made same or not
def flipsPossible(a, n) :
 
    count_odd = 0; count_even = 0;
 
    # Iterate and count the parity
    for i in range(n) :
 
        # Odd
        if (a[i] & 1) :
            count_odd += 1;
 
        # Even
        else :
            count_even += 1;
 
    # Condition check
    if (count_odd % 2 and count_even % 2) :
        return False;
    else :
        return True;
 
# Driver Code
if __name__ == "__main__" :
 
    a = [ 1, 0, 1, 1, 0, 1 ];
     
    n = len(a);
 
    if (flipsPossible(a, n)) :
        print("Yes");
    else :
        print("No");
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to check if parity
    // can be made same or not
    static bool flipsPossible(int []a, int n)
    {
     
        int count_odd = 0, count_even = 0;
     
        // Iterate and count the parity
        for (int i = 0; i < n; i++)
        {
     
            // Odd
            if ((a[i] & 1) == 1)
                count_odd++;
     
            // Even
            else
                count_even++;
        }
     
        // Condition check
        if (count_odd % 2 == 1 && count_even % 2 == 1)
            return false;
     
        else
            return true;
    }
     
    // Drivers code
    public static void Main(String[] args)
    {
        int []a = { 1, 0, 1, 1, 0, 1 };
        int n = a.Length;
     
        if (flipsPossible(a, n))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation of the approach
 
     
// Function to check if parity
// can be made same or not
function flipsPossible(a, n){
 
 
    let count_odd = 0;
    let count_even = 0;
 
    // Iterate and count the parity
    for (let i = 0; i < n; i++)
    {
 
        // Odd
        if ((a[i] & 1) == 1)
            count_odd++;
        // Even
        else
            count_even++;
    }
     
    // Condition check
    if (count_odd % 2 == 1 && count_even % 2 == 1)
        return false;
    else
        return true;
}
     
// Drivers code
 
let a = [1, 0, 1, 1, 0, 1];
let n = a.length;
 
if (flipsPossible(a, n))
    document.write("Yes");
else
    document.write("No");
     
</script>

Yes

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)