Elementos mínimos a eliminar para que el cómputo de 0 y 1 sea igual

Dados dos arreglos binarios A y B de igual longitud, la tarea es encontrar el número mínimo de elementos que se eliminarán, desde el frente, para que la cuenta de 0 y 1 sea igual en los dos arreglos binarios dados.

Ejemplos: 

Entrada: A = {0, 1, 0, 1, 1, 0}, B = {1, 0, 0, 1, 1, 1} 
Salida: 6 
Explicación: 
-> Eliminar los primeros 5 elementos de la array A 
-> Eliminar el primer elemento de B. 
-> Por lo tanto, se necesitan eliminar al menos 6 elementos para que el número total de 1 y 0 sea igual.

Entrada: a = {1, 0}, b = {0, 1} 
Salida: 0 
Explicación: 
La cuenta de 1 y 0 ya es igual. Por lo tanto, no es necesario eliminar ningún elemento. 

Enfoque: La idea es encontrar la diferencia entre el número total de 1 y el número total de 0 por separado y minimizando esta diferencia. Eliminar 1 disminuirá la diferencia en 1 y eliminar 0 aumentará la diferencia en 1. 
Por lo tanto, los pasos necesarios para hacer que la diferencia sea igual a 0 son: 

• Cuente la diferencia inicial en el número total de 1 y 0 . Llamémoslo initial_diff .
• Elimine los primeros l elementos de la primera array y almacene la diferencia en una variable left_diff .
• Elimine los primeros r elementos de la segunda array y almacene la diferencia en una variable right_diff.
• Ahora encuentre tales valores de l y r tales que:

initial_diff – left_diff – right_diff = 0.

• Para encontrar l y r de manera óptima, para cada valor único de right_diff, guarde la r más pequeña para alcanzar este valor en un mapa unordered_map . Luego, finalmente, itera sobre l para encontrar la respuesta mínima.

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

// C++ program to find minimum elements
// to be removed to make count
// of 0s and 1s equal
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns minimum elements
// need to be removed
int MinRemovedElements(int a[], int b[],
                    int n)
{
 
    int no_of_ones = 0;
    int no_of_zeroes = 0;
 
    // Counting total number of
    // zeroes and ones
    for (int i = 0; i < n; i++) {
        if (a[i] == 1)
            no_of_ones++;
        else
            no_of_zeroes++;
 
        if (b[i] == 1)
            no_of_ones++;
        else
            no_of_zeroes++;
    }
 
    // Computing difference in ones and
    // zeroes
    int diff = no_of_ones - no_of_zeroes;
 
    unordered_map<int, int> mp;
    mp[0] = 0;
    int curr = 0;
 
    // Filling the difference of number
    // of 1's and 0's of 1st array in
    // unoredered_map
    for (int i = 0; i < n; i++) {
        if (a[i] == 1)
            curr++;
        else
            curr--;
 
        // Condition if current difference
        // not found in map
        if (mp.find(curr) == mp.end())
            mp[curr] = i + 1;
    }
 
    curr = 0;
    int answer = 2 * n;
 
    for (int i = 0; i < n; i++) {
        if (b[i] == 1)
            curr++;
        else
            curr--;
 
        // Condition if current difference is
        // present in map then compute the
        // minimum one
        if (mp.find(diff - curr) != mp.end())
            answer
                = min(answer,
                    i + 1 + mp);
    }
 
    // Condition if the total difference
    // is present in 1st array
    if (mp.find(diff) != mp.end())
        answer = min(answer, mp);
 
    return answer;
}
 
// Driver Code
int main()
{
    int a[] = { 0, 1, 0, 1, 1, 0 };
    int b[] = { 1, 0, 0, 1, 1, 1 };
    int size = sizeof(a) / sizeof(a[0]);
 
    cout << MinRemovedElements(a, b, size)
        << "\n";
 
    return 0;
}

// Java program to find minimum elements
// to be removed to make count
// of 0s and 1s equal
import java.util.*;
 
class GFG{
 
// Function that returns minimum elements
// need to be removed
static int MinRemovedElements(int a[], int b[],
                    int n)
{
 
    int no_of_ones = 0;
    int no_of_zeroes = 0;
 
    // Counting total number of
    // zeroes and ones
    for (int i = 0; i < n; i++) {
        if (a[i] == 1)
            no_of_ones++;
        else
            no_of_zeroes++;
 
        if (b[i] == 1)
            no_of_ones++;
        else
            no_of_zeroes++;
    }
 
    // Computing difference in ones and
    // zeroes
    int diff = no_of_ones - no_of_zeroes;
 
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
    mp.put(0, 0);
    int curr = 0;
 
    // Filling the difference of number
    // of 1's and 0's of 1st array in
    // unoredered_map
    for (int i = 0; i < n; i++) {
        if (a[i] == 1)
            curr++;
        else
            curr--;
 
        // Condition if current difference
        // not found in map
        if (!mp.containsKey(curr))
            mp.put(curr, i + 1);
    }
 
    curr = 0;
    int answer = 2 * n;
 
    for (int i = 0; i < n; i++) {
        if (b[i] == 1)
            curr++;
        else
            curr--;
 
        // Condition if current difference is
        // present in map then compute the
        // minimum one
        if (mp.containsKey(diff - curr))
            answer
                = Math.min(answer,mp.get(diff - curr) + 1 + i);
    }
 
    // Condition if the total difference
    // is present in 1st array
    if (mp.containsKey(diff))
        answer = Math.min(answer, mp.get(diff));
 
    return answer;
}
 
// Driver Code
public static void main(String[] args)
{
    int a[] = { 0, 1, 0, 1, 1, 0 };
    int b[] = { 1, 0, 0, 1, 1, 1 };
    int size = a.length;
 
    System.out.print(MinRemovedElements(a, b, size)
        + "\n");
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to find minimum
# elements to be removed to make
# count of 0s and 1s equal
 
# Function that returns minimum
# elements need to be removed
def MinRemovedElements(a, b, n):
 
    no_of_ones = 0;
    no_of_zeroes = 0;
 
    # Counting total number of
    # zeroes and ones
    for i in range(n):
        if (a[i] == 1):
            no_of_ones += 1;
        else:
            no_of_zeroes += 1;
 
        if (b[i] == 1):
            no_of_ones += 1;
        else:
            no_of_zeroes += 1;
 
    # Computing difference in ones and
    # zeroes
    diff1 = no_of_ones - no_of_zeroes;
 
    mp = {};
    mp[0] = 0;
    curr = 0;
 
    # Filling the difference of number
    # of 1's and 0's of 1st array in
    # unoredered_map
    for i in range(n):
        if (a[i] == 1):
            curr += 1;
        else :
            curr -= 1;
 
        # Condition if current difference
        # not found in map
        if curr not in mp:
            mp[curr] = i + 1;
     
    curr = 0;
    answer = 2 * n;
 
    for i in range(n):
        if (b[i] == 1):
            curr += 1;
        else:
            curr -= 1;
 
        # Condition if current difference is
        # present in map then compute the
        # minimum one
        if (diff1 - curr) in mp :
            answer = min(answer, i + 1 + mp[diff1 -
                                            curr]);
 
    # Condition if the total difference
    # is present in 1st array
    if diff1 in mp:
        answer = min(answer, mp[diff1]);
 
    return answer;
 
# Driver Code
if __name__ == "__main__" :
 
    a = [ 0, 1, 0, 1, 1, 0 ];
    b = [ 1, 0, 0, 1, 1, 1 ];
     
    size = len(a);
 
    print(MinRemovedElements(a, b, size));
     
# This code is contributed by Yash_R

// C# program to find minimum elements
// to be removed to make count
// of 0s and 1s equal
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function that returns minimum elements
// need to be removed
static int MinRemovedElements(int[] a, int[] b,
                              int n)
{
    int no_of_ones = 0;
    int no_of_zeroes = 0;
   
    // Counting total number of
    // zeroes and ones
    for(int i = 0; i < n; i++)
    {
        if (a[i] == 1)
            no_of_ones++;
        else
            no_of_zeroes++;
   
        if (b[i] == 1)
            no_of_ones++;
        else
            no_of_zeroes++;
    }
   
    // Computing difference in ones and
    // zeroes
    int diff = no_of_ones - no_of_zeroes;
     
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
                                         
    mp.Add(0, 0);
    int curr = 0;
   
    // Filling the difference of number
    // of 1's and 0's of 1st array in
    // unoredered_map
    for(int i = 0; i < n; i++)
    {
        if (a[i] == 1)
            curr++;
        else
            curr--;
   
        // Condition if current difference
        // not found in map
        if (!mp.ContainsKey(curr))
            mp.Add(curr, i + 1);
    }
   
    curr = 0;
    int answer = 2 * n;
   
    for(int i = 0; i < n; i++)
    {
        if (b[i] == 1)
            curr++;
        else
            curr--;
   
        // Condition if current difference is
        // present in map then compute the
        // minimum one
        if (mp.ContainsKey(diff - curr))
            answer = Math.Min(answer,
             i + 1 + mp);
    }
   
    // Condition if the total difference
    // is present in 1st array
    if (mp.ContainsKey(diff))
        answer = Math.Min(answer, mp);
   
    return answer;
}
 
// Driver code
static void Main()
{
    int[] a = { 0, 1, 0, 1, 1, 0 };
    int[] b = { 1, 0, 0, 1, 1, 1 };
    int size = a.Length;
      
    Console.WriteLine(MinRemovedElements(
        a, b, size));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
// Javascript program to find minimum elements
// to be removed to make count
// of 0s and 1s equal
 
// Function that returns minimum elements
// need to be removed
function MinRemovedElements(a, b, n)
{
 
    let no_of_ones = 0;
    let no_of_zeroes = 0;
 
    // Counting total number of
    // zeroes and ones
    for (let i = 0; i < n; i++) {
        if (a[i] == 1)
            no_of_ones++;
        else
            no_of_zeroes++;
 
        if (b[i] == 1)
            no_of_ones++;
        else
            no_of_zeroes++;
    }
 
    // Computing difference in ones and
    // zeroes
    let diff = no_of_ones - no_of_zeroes;
 
    let mp = new Map();
    mp.set(0 , 0);
    let curr = 0;
 
    // Filling the difference of number
    // of 1's and 0's of 1st array in
    // unoredered_map
    for (let i = 0; i < n; i++) {
        if (a[i] == 1)
            curr++;
        else
            curr--;
 
        // Condition if current difference
        // not found in map
        if (!mp.has(curr))
            mp.set(curr, i + 1);
    }
 
    curr = 0;
    let answer = 2 * n;
 
    for (let i = 0; i < n; i++) {
        if (b[i] == 1)
            curr++;
        else
            curr--;
 
        // Condition if current difference is
        // present in map then compute the
        // minimum one
        if (mp.has(diff - curr))
            answer = Math.min(answer, mp.get(diff - curr) + i + 1);
    }
 
    // Condition if the total difference
    // is present in 1st array
    if (mp.has(diff))
        answer = Math.min(answer, mp.get(diff));
 
    return answer;
}
 
// Driver Code
 
let a = [ 0, 1, 0, 1, 1, 0 ];
let b = [ 1, 0, 0, 1, 1, 1 ];
let size = a.length;
 
document.write(MinRemovedElements(a, b, size) + "<br>");
 
// This code is contributed by _saurabh_jaiswal
</script>

Producción:

6

Complejidad del tiempo: O(N)