Reorganice los elementos de la array para maximizar la suma de MEX de todas las arrays de prefijos

Dada una array arr[] de tamaño N , la tarea es reorganizar los elementos de la array de modo que la suma de MEX de todas las arrays de prefijos sea la máxima posible.

Nota: MEX de una secuencia es el número mínimo no negativo que no está presente en la secuencia. 

Ejemplos:

Entrada: arr[] = {2, 0, 1}
Salida: 0, 1, 2
Explicación:
Suma de MEX de todas las arrays de prefijos de todas las permutaciones posibles de la array dada:
arr[] = {0, 1, 2}, Mex(0) + Mex(0, 1) + Mex(0, 1, 2) = 1 + 2 + 3 = 6
arr[] = {1, 0, 2}, Mex(1) + Mex(1, 0 ) + Mex(1, 0, 2) = 0 + 2 + 3 = 5
arr[] = {2, 0, 1}, Mex(2) + Mex(2, 0) + Mex(2, 0, 1) = 0 + 1 + 3 = 4
arr[] = {0, 2, 1}, Mex(0) + Mex(0, 2) + Mex(0, 2, 1) = 1 + 1 + 3 = 5
arr[ ] = {1, 2, 0}, Mex(1) + Mex(1, 2) + Mex(1, 2, 0) = 0 + 0 + 3 = 3
arr[] = {2, 1, 0}, Mex(2) + Mex(2, 1) + Mex(2, 1, 0) = 0 + 0 + 3 = 3
Por lo tanto, la suma máxima posible es 6.

Entrada: arr[] = {1, 0, 0}
Salida: 0, 1, 0
Explicación:
Suma de MEX de todas las arrays de prefijos de todas las permutaciones posibles de la array dada:
arr[]={1, 0, 0}, Méx(1) + Méx(1, 0) + Méx(1, 0, 0) = 0 + 2 + 2 = 4
arr[]={0, 1, 0}, Méx(0) + Méx(0, 1 ) + Mex(0, 1, 0) = 1 + 2 + 2 = 5
arr[]={0, 0, 1}, Mex(0) + Mex(0, 0) + Mex(0, 0, 1) = 1 + 1 + 2 = 4
Por lo tanto, el valor máximo es 5 para el arreglo, arr[]={0, 1, 0}.

Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones posibles de la array dada arr[] y luego, para cada permutación, encontrar el valor de MEX de todas las arrays de prefijos, mientras realiza un seguimiento del valor máximo general. Después de iterar sobre todas las permutaciones posibles, imprima la permutación que tenga el valor más grande.

Complejidad temporal: O(N ² * N!)
Espacio auxiliar: O(N)

Enfoque eficiente: la idea óptima se basa en la observación de que la suma de MEX de arrays de prefijos será máxima cuando todos los elementos distintos se ordenen en orden creciente y los duplicados estén presentes al final de la array. 
Siga los pasos a continuación para resolver el problema:

• Inicialice un vector de enteros , digamos ans, para almacenar el arreglo requerido.
• Ordene la array arr[] en orden creciente .
• Recorra la array arr[] y empuje todos los elementos distintos en la array ans[] .
• Recorra nuevamente la array arr[] y coloque todos los elementos duplicados restantes en la array ans[] .
• Después de completar los pasos anteriores, imprima la array ans[] .

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 maximum sum of
// MEX of prefix arrays for any
// arrangement of the given array
void maximumMex(int arr[], int N)
{
 
    // Stores the final arrangement
    vector<int> ans;
 
    // Sort the array in increasing order
    sort(arr, arr + N);
 
    // Iterate over the array arr[]
    for (int i = 0; i < N; i++) {
        if (i == 0 || arr[i] != arr[i - 1])
            ans.push_back(arr[i]);
    }
 
    // Iterate over the array, arr[]
    // and push the remaining occurrences
    // of the elements into ans[]
    for (int i = 0; i < N; i++) {
        if (i > 0 && arr[i] == arr[i - 1])
            ans.push_back(arr[i]);
    }
 
    // Print the array, ans[]
    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";
}
 
// Driver Code
int main()
{
 
    // Given array
    int arr[] = { 1, 0, 0 };
 
    // Store the size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    maximumMex(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.Arrays;  
 
class GFG{
     
// Function to find the maximum sum of
// MEX of prefix arrays for any
// arrangement of the given array
static void maximumMex(int arr[], int N)
{
     
    // Stores the final arrangement
    int ans[] = new int[2 * N];
 
    // Sort the array in increasing order
    Arrays.sort(ans);
    int j = 0;
     
    // Iterate over the array arr[]
    for(int i = 0; i < N; i++)
    {
        if (i == 0 || arr[i] != arr[i - 1])
        {
            j += 1;
            ans[j] = arr[i];
        }
    }
 
    // Iterate over the array, arr[]
    // and push the remaining occurrences
    // of the elements into ans[]
    for(int i = 0; i < N; i++)
    {
        if (i > 0 && arr[i] == arr[i - 1])
        {
            j += 1;
            ans[j] = arr[i];
        }
    }
 
    // Print the array, ans[]
    for(int i = 0; i < N; i++)
        System.out.print(ans[i] + " ");
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given array
    int arr[] = { 1, 0, 0 };
 
    // Store the size of the array
    int N = arr.length;
 
    // Function Call
    maximumMex(arr, N);
}
}
 
// This code is contributed by AnkThon

# Python3 program for the above approach
 
# Function to find the maximum sum of
# MEX of prefix arrays for any
# arrangement of the given array
def maximumMex(arr, N):
 
    # Stores the final arrangement
    ans = []
 
    # Sort the array in increasing order
    arr = sorted(arr)
 
    # Iterate over the array arr[]
    for i in range(N):
        if (i == 0 or arr[i] != arr[i - 1]):
            ans.append(arr[i])
 
    # Iterate over the array, arr[]
    # and push the remaining occurrences
    # of the elements into ans[]
    for i in range(N):
        if (i > 0 and arr[i] == arr[i - 1]):
            ans.append(arr[i])
 
    # Print the array, ans[]
    for i in range(N):
        print(ans[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr = [1, 0, 0 ]
 
    # Store the size of the array
    N = len(arr)
 
    # Function Call
    maximumMex(arr, N)
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the maximum sum of
// MEX of prefix arrays for any
// arrangement of the given array
static void maximumMex(int []arr, int N)
{
     
    // Stores the final arrangement
    int []ans = new int[2 * N];
 
    // Sort the array in increasing order
    Array.Sort(ans);
    int j = 0;
     
    // Iterate over the array arr[]
    for(int i = 0; i < N; i++)
    {
        if (i == 0 || arr[i] != arr[i - 1])
        {
            j += 1;
            ans[j] = arr[i];
        }
    }
 
    // Iterate over the array, arr[]
    // and push the remaining occurrences
    // of the elements into ans[]
    for(int i = 0; i < N; i++)
    {
        if (i > 0 && arr[i] == arr[i - 1])
        {
            j += 1;
            ans[j] = arr[i];
        }
    }
 
    // Print the array, ans[]
    for(int i = 0; i < N; i++)
        Console.Write(ans[i] + " ");
}
 
// Driver Code
public static void Main (string[] args)
{
     
    // Given array
    int []arr = { 1, 0, 0 };
 
    // Store the size of the array
    int N = arr.Length;
 
    // Function Call
    maximumMex(arr, N);
}
}
 
// This code is contributed by AnkThon

<script>
 
// Javascript program for the above approach
 
// Function to find the maximum sum of
// MEX of prefix arrays for any
// arrangement of the given array
function maximumMex(arr, N)
{
 
    // Stores the final arrangement
    var ans = [];
 
    // Sort the array in increasing order
    arr.sort();
    var i;
    // Iterate over the array arr[]
    for (i = 0; i < N; i++) {
        if (i == 0 || arr[i] != arr[i - 1])
            ans.push(arr[i]);
    }
 
    // Iterate over the array, arr[]
    // and push the remaining occurrences
    // of the elements into ans[]
    for (i = 0; i < N; i++) {
        if (i > 0 && arr[i] == arr[i - 1])
            ans.push(arr[i]);
    }
 
    // Print the array, ans[]
    for (i = 0; i < N; i++)
        document.write(ans[i] + " ");
}
 
// Driver Code
    // Given array
    var arr = [1, 0, 0];
 
    // Store the size of the array
    var N = arr.length;
 
    // Function Call
    maximumMex(arr, N);
 
</script>

0 1 0

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)