Dada una array binaria arr[] de tamaño N , la tarea es encontrar el recuento máximo de 0 s que se puede convertir en 1 s de modo que ningún par de elementos de array adyacentes sean 1 .
Ejemplos:
Entrada: arr[] = { 1, 0, 0, 0, 1 }
Salida: 1
Explicación:
Actualizar arr[2] a 1 modifica arr[] a { 1, 0, 1, 0, 1 }
Por lo tanto, la salida requerida es 1Entrada: arr[] = { 0, 0, 1, 0, 0, 0, 0, 1, 0, 0 }
Salida: 3
Explicación:
Actualizar arr[0], arr[5] y arr[9] modifica arr[ ] a { 1, 0, 1, 0, 0, 1, 0, 1, 0, 1 }
Por lo tanto, la salida requerida es 3
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inserte 0 al principio y al final de la array .
- Atraviesa la array, arr[] . En cada i-ésima iteración, verifique si arr[i] , arr[i + 1] y arr[i + 2] son 0 s o no. Si se encuentra que es cierto, entonces incremente el conteo y actualice arr[i + 1] = 1 .
- Finalmente, imprima el conteo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum count of 0s
// required to be converted into 1s such
// no pair of adjacent elements are 1
void maxPositionsOccupied(vector<int>& arr)
{
// Base Case
if (arr.size() == 0) {
cout << 0;
return;
}
// Insert 0 at the end
// of the array
arr.push_back(0);
// Insert 0 at the front
// of the array
arr.insert(arr.begin(), 0);
// Stores the maximum count of 0s
// that can be converted into 1s
int ans = 0;
// Stores index of array elements
int i = 0;
// Traverse the array
while ((i < arr.size() - 2)) {
// If adjacent elements are 0s
if ((arr[i] == 0) && (arr[i + 1] == 0)
&& (arr[i + 2] == 0)) {
// Update ans
ans++;
// Update arr[i + 1]
arr[i + 1] = 1;
}
// Update i
i++;
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
// Given binary array
vector<int> arr = { 1, 0, 0, 0, 1 };
// Prints the maximum 0 to 1
// conversions required
maxPositionsOccupied(arr);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to find the maximum count of 0s
// required to be converted into 1s such
// no pair of adjacent elements are 1
static void maxPositionsOccupied(int[] arr)
{
// Base Case
if (arr.length == 0)
{
System.out.print(0);
return;
}
// Stores the maximum count of 0s
// that can be converted into 1s
int ans = 0;
// Stores index of array elements
int i = 0;
// Traverse the array
while ((i < arr.length - 2))
{
// If adjacent elements are 0s
if ((arr[i] == 0) &&
(arr[i + 1] == 0) &&
(arr[i + 2] == 0))
{
// Update ans
ans++;
// Update arr[i + 1]
arr[i + 1] = 1;
}
// Update i
i++;
}
// Print the answer
System.out.print(ans);
}
// Driver code
public static void main(String[] args)
{
// Given binary array
int[] arr = { 1, 0, 0, 0, 1 };
// Prints the maximum 0 to 1
// conversions required
maxPositionsOccupied(arr);
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python3 program for the above approach # Function to find the maximum count of 0s # required to be converted into 1s such # no pair of adjacent elements are 1 def maxPositionsOccupied(arr): # Base Case if (len(arr) == 0): print(0) # Insert 0 at the end # of the array arr.append(0) # Insert 0 at the front # of the array arr.insert(0, 0) # Stores the maximum count of 0s # that can be converted into 1s ans = 0 # Stores index of array elements i = 0 # Traverse the array while((i < len(arr) - 2)): # If adjacent elements are 0s if ((arr[i] == 0) and (arr[i + 1] == 0) and (arr[i + 2] == 0)): # Update ans ans += 1 # Update arr[i + 1] arr[i + 1] = 1 # Update i i += 1 # Print the answer print(ans) # Driver Code if __name__ == '__main__': # Given binary array arr = [ 1, 0, 0, 0, 1 ] # Prints the maximum 0 to 1 # conversions required maxPositionsOccupied(arr) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum count of 0s
// required to be converted into 1s such
// no pair of adjacent elements are 1
static void maxPositionsOccupied(int[] arr)
{
// Base Case
if (arr.Length == 0)
{
Console.Write(0);
return;
}
// Stores the maximum count of 0s
// that can be converted into 1s
int ans = 0;
// Stores index of array elements
int i = 0;
// Traverse the array
while ((i < arr.Length - 2))
{
// If adjacent elements are 0s
if ((arr[i] == 0) &&
(arr[i + 1] == 0) &&
(arr[i + 2] == 0))
{
// Update ans
ans++;
// Update arr[i + 1]
arr[i + 1] = 1;
}
// Update i
i++;
}
// Print the answer
Console.Write(ans);
}
// Driver code
static void Main()
{
// Given binary array
int[] arr = { 1, 0, 0, 0, 1 };
// Prints the maximum 0 to 1
// conversions required
maxPositionsOccupied(arr);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum count of 0s
// required to be converted into 1s such
// no pair of adjacent elements are 1
function maxPositionsOccupied(arr)
{
// Base Case
if (arr.length == 0)
{
document.write(0);
return;
}
// Stores the maximum count of 0s
// that can be converted into 1s
let ans = 0;
// Stores index of array elements
let i = 0;
// Traverse the array
while ((i < arr.length - 2))
{
// If adjacent elements are 0s
if ((arr[i] == 0) &&
(arr[i + 1] == 0) &&
(arr[i + 2] == 0))
{
// Update ans
ans++;
// Update arr[i + 1]
arr[i + 1] = 1;
}
// Update i
i++;
}
// Print the answer
document.write(ans);
}
// Given binary array
let arr = [ 1, 0, 0, 0, 1 ];
// Prints the maximum 0 to 1
// conversions required
maxPositionsOccupied(arr);
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)