Número mínimo de 1 que se reemplazarán en una array binaria

Dada una array binaria arr[] de ceros y uno solamente. La tarea es encontrar el número mínimo de uno que se cambiará a cero, de modo que si existe algún índice  en la array tal que arr[i] = 0, entonces arr[i-1] y arr[i+1] no deberían ser ambos. es igual a  al mismo tiempo.
Es decir, para cualquier índice,  la siguiente condición debería fallar: 
 

if (arr[i]== 0):
    (arr[i-1] == 1) && (arr[i+1] == 1)

Nota : la indexación basada en 1 se considera para la array.
Ejemplos : 
 

Entrada : arr[] = { 1, 1, 0, 1, 1, 0, 1, 0, 1, 0 } 
Salida : 2 
Explicación : Los índices 2 y 7 O 4 y 7 se pueden cambiar a cero.
Entrada : arr[] = { 1, 1, 0, 0, 0 } 
Salida : 0 
 

Enfoque: la idea es que, cada vez que encontramos una condición como  , simplemente cambiamos el valor del índice (i+1) a cero (0). Entonces ese índice entre (i-1)-ésimo y (i+1)-ésimo índice es seguro.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find minimum number
// of 1's  to be replaced to 0's
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum number
// of 1's  to be replaced to 0's
int minChanges(int A[], int n)
{
    int cnt = 0;
 
    for (int i = 0; i < n - 2; ++i) {
 
        if ((i - 1 >= 0) && A[i - 1] == 1
            && A[i + 1] == 1 && A[i] == 0) {
            A[i + 1] = 0;
            cnt++;
        }
 
    }
 
    // return final answer
    return cnt;
}
 
// Driver program
int main()
{
    int A[] = { 1, 1, 0, 1, 1, 0, 1, 0, 1, 0 };
    int n = sizeof(A) / sizeof(A[0]);
 
    cout << minChanges(A, n);
 
    return 0;
}

// Java program to find minimum number
// of 1's to be replaced to 0's
import java.lang.*;
import java.util.*;
 
class GFG
{
// Function to find minimum number
// of 1's to be replaced to 0's
static int minChanges(int[] A, int n)
{
    int cnt = 0;
 
    for (int i = 0; i < n - 2; ++i)
    {
 
        if ((i - 1 >= 0) && A[i - 1] == 1 &&
                            A[i + 1] == 1 &&
                            A[i] == 0)
        {
            A[i + 1] = 0;
            cnt++;
        }
 
    }
 
    // return final answer
    return cnt;
}
 
// Driver Code
public static void main(String args[])
{
    int[] A = { 1, 1, 0, 1, 1, 0, 1, 0, 1, 0 };
    int n = A.length;
 
    System.out.print(minChanges(A, n));
}
}
 
// This code is contributed
// by Akanksha Rai

# Python 3 program to find minimum
# number of 1's to be replaced to 0's
     
# Function to find minimum number
# of 1's to be replaced to 0's
def minChanges(A, n):
    cnt = 0
    for i in range(n - 2):
        if ((i - 1 >= 0) and A[i - 1] == 1 and
           A[i + 1] == 1 and A[i] == 0):
            A[i + 1] = 0
            cnt = cnt + 1
     
    # return final answer
    return cnt
     
# Driver Code
A = [1, 1, 0, 1, 1, 0, 1, 0, 1, 0]
n = len(A)
print(minChanges(A, n))
         
# This code is contributed
# by Shashank_Sharma

// C# program to find minimum number
// of 1's to be replaced to 0's
using System;
 
class GFG
{
// Function to find minimum number
// of 1's to be replaced to 0's
static int minChanges(int[] A, int n)
{
    int cnt = 0;
 
    for (int i = 0; i < n - 2; ++i)
    {
 
        if ((i - 1 >= 0) && A[i - 1] == 1 &&
                            A[i + 1] == 1 && A[i] == 0)
        {
            A[i + 1] = 0;
            cnt++;
        }
 
    }
 
    // return final answer
    return cnt;
}
 
// Driver Code
public static void Main()
{
    int[] A = { 1, 1, 0, 1, 1, 0, 1, 0, 1, 0 };
    int n = A.Length;
 
    Console.Write(minChanges(A, n));
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP program to find minimum number
// of 1's to be replaced to 0's
 
// Function to find minimum number
// of 1's to be replaced to 0's
function minChanges($A, $n)
{
    $cnt = 0;
 
    for ($i = 0; $i < $n - 2; ++$i)
    {
        if (($i - 1 >= 0) && $A[$i - 1] == 1 &&
          $A[$i + 1] == 1 && $A[$i] == 0)
        {
            $A[$i + 1] = 0;
            $cnt++;
        }
 
    }
 
    // return final answer
    return $cnt;
}
 
// Driver Code
$A = array(1, 1, 0, 1, 1,
           0, 1, 0, 1, 0);
$n = sizeof($A);
 
echo minChanges($A, $n);
 
// This code is contributed
// by Ankita_Saini
?>

<script>
 
// Javascript program to find minimum number
// of 1's  to be replaced to 0's
 
// Function to find minimum number
// of 1's  to be replaced to 0's
function minChanges(A, n)
{
    var cnt = 0;
 
    for (var i = 0; i < n - 2; ++i) {
 
        if ((i - 1 >= 0) && A[i - 1] == 1
            && A[i + 1] == 1 && A[i] == 0) {
            A[i + 1] = 0;
            cnt++;
        }
 
    }
 
    // return final answer
    return cnt;
}
 
 
var A = [ 1, 1, 0, 1, 1, 0, 1, 0, 1, 0 ];
var n = A.length;
document.write(  minChanges(A, n));
 
 
// This code is contributed by SoumikMondal
 
</script>

2

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)