Dada una array arr[] que consta de solo 0 y 1 . La tarea es encontrar el número mínimo de eliminaciones desde el frente y el reverso de la array, de modo que la nueva array modificada consista en un número igual de 0 y 1.
Ejemplos:
Entrada : arr[] = {1, 1, 0, 1}
Salida : 2
Explicación : se pueden eliminar dos unos del elemento inicial o el primero y el últimoEntrada : arr[] = {0, 1, 1, 1, 0}
Salida : 3
Explicación : los primeros tres elementos se pueden eliminar o los últimos tres elementos
Enfoque : el problema se puede resolver utilizando un enfoque codicioso. Como cada elemento de la array puede ser 0 o 1, considere 0 como -1 y 1 como 1 en sí mismo. Luego encuentre el subarreglo más grande que consta de un número igual de 1 y 0. Luego reste el tamaño de este subarreglo del tamaño total del arreglo. Este enfoque funciona porque en cualquier momento intenta mantener el tamaño del subarreglo lo más grande posible para que solo se pueda eliminar una cantidad mínima de elementos de los extremos. Consulte el siguiente diagrama para una mejor comprensión.
Como se puede ver en el diagrama, a medida que aumenta el tamaño de la parte central y , que consta de un número igual de 0 y 1 , automáticamente disminuye el tamaño de la parte (x + z).
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// the minimum number of deletions
int solve(vector<int> arr)
{
// Size of the array
int sz = arr.size();
// Store running sum of array
int summe = 0;
// To store index of the sum
unordered_map<int, int> index;
// Initially sum is 0 with index -1
index[summe] = -1;
// Store length of largest subarray
int ans = 0, curr_len = 0;
for (int i = 0; i < sz; i++) {
// If curr_element is 0, add -1
if (arr[i] == 0)
summe -= 1;
// If curr_element is 1, add 1
else
summe += 1;
// Check if sum already occurred
if (index.find(summe) != index.end()) {
// Calculate curr subarray length
curr_len = i - index[summe];
// Store the maximum value
// in the ans
ans = max(ans, curr_len);
}
// Sum occurring for the first time
// So store this sum with current index
else
index[summe] = i;
}
// Return diff between size
// and largest subarray
return (sz - ans);
}
// Driver code
int main()
{
vector<int> arr = { 1, 1, 0, 1 };
int val = solve(arr);
cout << val;
}
// This code is contributed by Samim Hossain Mondal.
Java
// Java code for the above approach
import java.util.*;
class GFG{
// Function to calculate
// the minimum number of deletions
static int solve(int[] arr)
{
// Size of the array
int sz = arr.length;
// Store running sum of array
int summe = 0;
// To store index of the sum
HashMap<Integer,Integer> index = new HashMap<Integer,Integer>();
// Initially sum is 0 with index -1
index.put(summe, -1);
// Store length of largest subarray
int ans = 0, curr_len = 0;
for (int i = 0; i < sz; i++) {
// If curr_element is 0, add -1
if (arr[i] == 0)
summe -= 1;
// If curr_element is 1, add 1
else
summe += 1;
// Check if sum already occurred
if (index.containsKey(summe) ) {
// Calculate curr subarray length
curr_len = i - index.get(summe);
// Store the maximum value
// in the ans
ans = Math.max(ans, curr_len);
}
// Sum occurring for the first time
// So store this sum with current index
else
index.put(summe, i);
}
// Return diff between size
// and largest subarray
return (sz - ans);
}
// Driver code
public static void main(String[] args)
{
int []arr = { 1, 1, 0, 1 };
int val = solve(arr);
System.out.print(val);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python code to implement the given approach from collections import defaultdict class Solution: # Function to calculate # the minimum number of deletions def solve(self, arr): # Size of the array size = len(arr) # Store running sum of array summe = 0 # To store index of the sum index = defaultdict(int) # Initially sum is 0 with index -1 index[summe] = -1 # Store length of largest subarray ans = 0 for i in range(size): # If curr_element is 0, add -1 if (arr[i] == 0): summe -= 1 # If curr_element is 1, add 1 else: summe += 1 # Check if sum already occurred if (summe in index): # Calculate curr subarray length curr_len = i - index[summe] # Store the maximum value # in the ans ans = max(ans, curr_len) # Sum occurring for the first time # So store this sum with current index else: index[summe] = i # Return diff between size # and largest subarray return (size - ans) if __name__ == "__main__": arr = [1, 1, 0, 1] obj = Solution() val = obj.solve(arr) print(val)
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate
// the minimum number of deletions
static int solve(int[] arr)
{
// Size of the array
int sz = arr.Length;
// Store running sum of array
int summe = 0;
// To store index of the sum
Dictionary<int,int> index = new Dictionary<int, int>();
// Initially sum is 0 with index -1
index.Add(summe, -1);
// Store length of largest subarray
int ans = 0, curr_len = 0;
for (int i = 0; i < sz; i++) {
// If curr_element is 0, add -1
if (arr[i] == 0)
summe -= 1;
// If curr_element is 1, add 1
else
summe += 1;
// Check if sum already occurred
if (index.ContainsKey(summe) ) {
// Calculate curr subarray length
curr_len = i - index[summe];
// Store the maximum value
// in the ans
ans = Math.Max(ans, curr_len);
}
// Sum occurring for the first time
// So store this sum with current index
else
index[summe] = i;
}
// Return diff between size
// and largest subarray
return (sz - ans);
}
// Driver code
public static void Main()
{
int []arr = { 1, 1, 0, 1 };
int val = solve(arr);
Console.Write(val);
}
}
// This code is contributed by gfgking
Javascript
<script>
// JavaScript code for the above approach
// Function to calculate
// the minimum number of deletions
function solve(arr)
{
// Size of the array
size = arr.length
// Store running sum of array
let summe = 0
// To store index of the sum
index = new Map();
// Initially sum is 0 with index -1
index.set(summe, -1);
// Store length of largest subarray
ans = 0
for (let i = 0; i < size; i++) {
// If curr_element is 0, add -1
if (arr[i] == 0)
summe -= 1
// If curr_element is 1, add 1
else
summe += 1
// Check if sum already occurred
if (index.has(summe)) {
// Calculate curr subarray length
curr_len = i - index.get(summe)
// Store the maximum value
// in the ans
ans = Math.max(ans, curr_len)
}
// Sum occurring for the first time
// So store this sum with current index
else
index.set(summe, i)
}
// Return diff between size
// and largest subarray
return (size - ans)
}
// Driver code
arr = [1, 1, 0, 1]
val = solve(arr)
document.write(val)
// This code is contributed by Potta Lokesh
</script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)