Verifique si los K 0 se pueden voltear de manera que la array dada no tenga 1 adyacentes

Dada una array binaria arr[] de tamaño N y un número entero K , la tarea es verificar si los K 0 se pueden invertir de manera que la array no tenga 1 adyacentes.

Ejemplos:

Entrada: arr[] = {0, 0, 0, 0, 1}, K=2
Salida: verdadero
Explicación: El 0 en los índices 0 y 2 se puede reemplazar por 1. 
Por lo tanto, se pueden voltear 2 elementos (=K).

Entrada: arr[] = {1, 0, 0, 0, 1}, K = 2
Salida: false
Explicación: El 0 en el índice 2 se puede reemplazar por 1. 
Por lo tanto, se puede voltear 1 elemento (!= K).

Enfoque: La solución se basa en el enfoque codicioso . Por favor, siga los pasos que se mencionan a continuación:

• Itere sobre la array y para cada índice que tenga 0, verifique si sus dos índices adyacentes tienen 0 o no. Para cada posible lanzamiento, disminuya la cuenta de K.
• Para el último y el primer índice de la array, verifique el índice izquierdo y derecho adyacentes, respectivamente.
• Para cada índice que satisfaga la condición anterior, disminuya la cuenta de K si es posible.
• Devuelve verdadero si K<=0, de lo contrario devuelve falso.

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

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check
// the possibility of K flips
bool flips(vector<int>& arr, int K)
{
    if (arr[0] == 0 && (arr.size() == 1
                      || arr[1] == 0)) {
        arr[0] = 1;
        K--;
    }
 
    for (int i = 1; i < arr.size() - 1;
         i++) {
        if (arr[i - 1] == 0 && arr[i] == 0
            && arr[i + 1] == 0) {
            arr[i] = 1;
            K--;
        }
    }
 
    if (arr.size() > 1
        && arr[arr.size() - 2] == 0
        && arr[arr.size() - 1] == 0) {
        arr[arr.size() - 1] = 1;
        K--;
    }
 
    return K <= 0;
}
 
// Driver code
int main()
{
    vector<int> arr = { 0, 0, 0, 0, 1 };
    int K = 2;
    cout << (flips(arr, K) ? "true" : "false");
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to check
  // the possibility of K flips
  static Boolean flips(int arr[], int K)
  {
    if (arr[0] == 0 && (arr.length == 1
                        || arr[1] == 0)) {
      arr[0] = 1;
      K--;
    }
 
    for (int i = 1; i < arr.length - 1;
         i++) {
      if (arr[i - 1] == 0 && arr[i] == 0
          && arr[i + 1] == 0) {
        arr[i] = 1;
        K--;
      }
    }
 
    if (arr.length > 1
        && arr[arr.length - 2] == 0
        && arr[arr.length - 1] == 0) {
      arr[arr.length - 1] = 1;
      K--;
    }
 
    return K <= 0;
  }
 
  // Driver code
  public static void main (String[] args) {
    int arr[] = { 0, 0, 0, 0, 1 };
    int K = 2;
    System.out.println(flips(arr, K) ? "true" : "false");
  }
}
 
// This code is contributed by hrithikgarg03188

# Python code for the above approach
 
# Function to check
# the possibility of K flips
def flips(arr, K):
    if (arr[0] == 0 and (len(arr) == 1 or arr[1] == 0)):
        arr[0] = 1;
        K -= 1
 
    for i in range(1, len(arr) - 1):
        if (arr[i - 1] == 0 and arr[i] == 0
            and arr[i + 1] == 0):
            arr[i] = 1;
            K -= 1
 
    if (len(arr) > 1
        and arr[len(arr) - 2] == 0
        and arr[len(arr) - 1] == 0):
        arr[len(arr) - 1] = 1;
        K -= 1
 
    return K <= 0;
 
# Driver code
arr = [0, 0, 0, 0, 1];
K = 2;
if (flips(arr, K)):
    print("true");
else:
    print("false");
 
# This code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
class GFG {
 
  // Function to check
  // the possibility of K flips
  static Boolean flips(int[] arr, int K)
  {
    if (arr[0] == 0 && (arr.Length == 1  || arr[1] == 0)) {
      arr[0] = 1;
      K--;
    }
 
    for (int i = 1; i < arr.Length - 1;
         i++) {
      if (arr[i - 1] == 0 && arr[i] == 0
          && arr[i + 1] == 0) {
        arr[i] = 1;
        K--;
      }
    }
 
    if (arr.Length > 1
        && arr[arr.Length - 2] == 0
        && arr[arr.Length - 1] == 0) {
      arr[arr.Length - 1] = 1;
      K--;
    }
 
    return K <= 0;
  }
 
  // Driver code
  public static void Main () {
    int[] arr = { 0, 0, 0, 0, 1 };
    int K = 2;
    Console.Write(flips(arr, K) ? "true" : "false");
  }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
       // JavaScript code for the above approach
 
       // Function to check
       // the possibility of K flips
       function flips(arr, K) {
           if (arr[0] == 0 && (arr.length == 1
               || arr[1] == 0)) {
               arr[0] = 1;
               K--;
           }
 
           for (let i = 1; i < arr.length - 1;
               i++) {
               if (arr[i - 1] == 0 && arr[i] == 0
                   && arr[i + 1] == 0) {
                   arr[i] = 1;
                   K--;
               }
           }
 
           if (arr.length > 1
               && arr[arr.length - 2] == 0
               && arr[arr.length - 1] == 0) {
               arr[arr.length - 1] = 1;
               K--;
           }
 
           return K <= 0;
       }
 
       // Driver code
 
       let arr = [0, 0, 0, 0, 1];
       let K = 2;
       if (flips(arr, K))
           document.write("true");
       else
           document.write("false");
 
        // This code is contributed by Potta Lokesh
   </script>

true

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