Operaciones mínimas para las que todos los enteros de [0, N] aparecen como el número faltante positivo más pequeño (MEX)

Dada una array arr[] , de tamaño N , la tarea es encontrar las operaciones mínimas en la array de modo que en cada operación cualquier elemento de la array pueda elegirse e incrementarse en 1 para que MEX sea i para todo i en el rango [0, n] . Si para cualquier i, si el MEX no es , imprimo -1 .

Ejemplos: 

Entrada: arr[] = {3, 0, 1, 0, 3}
Salida: 
MEX para i = 0 es 2
MEX para i = 1 es 1
MEX para i = 2 es 0
MEX para i = 3 es 4
MEX para i = 4 es 2
MEX para i = 5 es 3
Explicación: 
Para MEX = 0 
En la operación 1 elija el índice 1 e increméntelo en 1 
En la operación 2 elija el índice 3 e increméntelo en 1 la array se convierte en {3, 1, 1, 1 , 3} MEX = 0. Entonces 2 operaciones.
Para MEX = 1
En la operación 1, elija el índice 2 e increméntelo en 1, la array se convierte en {3, 0, 2, 0, 3} MEX = 1. Entonces, 1 operación.
Para MEX = 2, Entonces 0 operación.
Ya está teniendo MEX = 2 
Para MEX = 3
En la operación 1 elige el índice 0 y lo incrementa en 1 
En la operación 2 elige el índice 3 y lo incrementa en 1
En la operación 3 elige el índice 1 y lo incrementa en 1  
En la operación 3 elige el índice 1 y lo incrementa en 1, la array se convierte en {4, 2, 1, 0, 4} MEX = 3 así que 4 operaciones.
Lo mismo para MEX = 4, 5 .

Entrada: {1, 2, 3, 4}
Salida: 0 -1, -1, -1, -1
MEX para i = 0 es 0
MEX para i = 1 es -1
MEX para i = 2 es -1
MEX para i = 3 es -1
MEX para i = 4 es -1

Enfoque: el hashing se puede usar para resolver este problema para almacenar las frecuencias del elemento y la pila se puede usar para almacenar los elementos repetidos en la array. Hashmap se puede usar para almacenar las frecuencias para un MEX = i si i ya existe en el hashmap, incremente todas las ocurrencias y almacene los elementos repetidos en la pila; de lo contrario, si la frecuencia de i es 0 , ya es un MEX , entonces 0 operaciones, ahora busque las ocurrencias repetitivas en la pila y conviértalas en i actual de modo que para i+1 , ino se convertiría en MEX . Siga estos pasos para resolver este problema:

• Inicialice un freq[] de unordered_map para almacenar las frecuencias de la array arr[] y una variable is_possible para realizar un seguimiento de la posibilidad de MEX .
• Itere a través de la array arr[] y almacene las frecuencias en el hashmap freq.
• Inicialice la pila stk[] y el vector ops , para almacenar las operaciones mínimas para MEX = i , prev_cost para almacenar el costo requerido para incrementar el elemento repetido.
• Si is_possible == 0 , MEX = i no es posible, así que almacene -1 .
• De lo contrario, almacene freq[i]+ prev_cost en ops .
  • Si freq[i] es igual a 0 Verifique si hay algún elemento en la pila, extráigalo e increméntelo a i e incremente prev_cost a ij e incremente freq[i] , si la pila está vacía, haga is_possible a false.
  • De lo contrario, si freq[i]>1 empuja el repetido en la pila stk[] y disminuye freq[i] .
• Ahora imprima el vector ops que contiene las operaciones mínimas para hacer MEX = i [0, n] .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum operations
// to make the MEX = i
void find_min_operations(int arr[], int n)
{
 
    // Initialize an unordered_map
    // to store the frequencies
    unordered_map<int, int> freq;
 
    // is_possible to store
    // the possibility of MEX = i
    bool is_possible = true;
 
    // count the frequencies
    // and store into the freq
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }
 
    // Initialize stack to store
    // the repeated elements
    stack<int> stk;
 
    // ops store the minimum
    // operations required for MEX =i
    vector<int> ops;
 
    // prev_cost to store the
    // cost to increment some
    // repeated element to i-1
    // if MEX initially is i-1 so
    // that  MEX remains i
    int prev_cost = 0;
    for (int i = 0; i <= n; i++) {
 
        // Push -1 if it is not possible
        if (is_possible == 0)
            ops.push_back(-1);
        else {
 
            ops.push_back(freq[i] + prev_cost);
 
            // If frequency of the element is 0
            // then check for repeated element
            // in the stack so that it can be added
            // with i-j operations in next iteration
            // and can be made it to i.
            if (freq[i] == 0) {
 
                // Check for repeated
                // element in the stack
                if (!stk.empty()) {
                    int j = stk.top();
                    stk.pop();
                    prev_cost += i - j;
                    // Increment the frequency of i since
                    // the repeated element j is made to i
 
                    freq[i]++;
                }
 
                // If no repeated element
                // no possibility for MEX = i+1
                // so make is_possible=false
                else
                    is_possible = false;
            }
 
            // If i is already available
            else {
 
                // Push the repeated elements
                // into the stack
                while (freq[i] > 1) {
                    stk.push(i);
                    freq[i]--;
                }
            }
        }
    }
 
    for (int i = 0; i < ops.size(); i++) {
        cout << "MEX for i = "
             << i << " is " << ops[i]
             << endl;
    }
}
 
// Driver Code
int main()
{
 
    // Initializing array arr[]
    int arr[] = { 3, 0, 1, 0, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    find_min_operations(arr, n);
    return 0;
}

# Python3 program for the above approach
from collections import deque
 
# Function to find the minimum operations
# to make the MEX = i
def find_min_operations(arr, n):
     
    # Initialize an unordered_map
    # to store the frequencies
    freq = {}
 
    # is_possible to store
    # the possibility of MEX = i
    is_possible = True
 
    # Count the frequencies
    # and store into the freq
    for i in range(0, n):
        if arr[i] in freq:
            freq[arr[i]] += 1
        else:
            freq[arr[i]] = 1
 
    # Initialize stack to store
    # the repeated elements
    stk = deque()
 
    # ops store the minimum
    # operations required for MEX =i
    ops = []
 
    # prev_cost to store the
    # cost to increment some
    # repeated element to i-1
    # if MEX initially is i-1 so
    # that MEX remains i
    prev_cost = 0
    for i in range(0, n + 1):
 
        # Push -1 if it is not possible
        if (is_possible == 0):
            ops.append(-1)
        else:
            if i in freq:
                ops.append(freq[i] + prev_cost)
            else:
                ops.append(prev_cost)
 
            # If frequency of the element is 0
            # then check for repeated element
            # in the stack so that it can be added
            # with i-j operations in next iteration
            # and can be made it to i.
            if (not (i in freq)):
 
                # Check for repeated
                # element in the stack
                if (len(stk) != 0):
                    j = stk.popleft()
                    prev_cost += i - j
                     
                    # Increment the frequency of i since
                    # the repeated element j is made to i
                    freq[i] = freq[i] + 1 if i in freq else 1
 
                # If no repeated element
                # no possibility for MEX = i+1
                # so make is_possible=false
                else:
                    is_possible = False
 
            # If i is already available
            else:
 
                # Push the repeated elements
                # into the stack
                while (freq[i] > 1):
                    stk.append(i)
                    freq[i] -= 1
 
    for i in range(0, len(ops)):
        print(f"MEX for i = {i} is {ops[i]}")
 
# Driver Code
if __name__ == "__main__":
 
    # Initializing array arr[]
    arr = [ 3, 0, 1, 0, 3 ]
    n = len(arr)
 
    # Function call
    find_min_operations(arr, n)
 
# This code is contributed by rakeshsahni

MEX for i = 0 is 2
MEX for i = 1 is 1
MEX for i = 2 is 0
MEX for i = 3 is 4
MEX for i = 4 is 2
MEX for i = 5 is 3

Complejidad de tiempo: O(N) donde N es el tamaño de la array
Espacio auxiliar: O(N)