Costo mínimo para vaciar la array donde el costo de eliminar un elemento es 2^(removed_count) * arr[i]

Dada una array arr[], la tarea es encontrar el costo mínimo para eliminar todos los elementos de la array donde el costo de eliminar un elemento es 2^j * arr[i]. Aquí, j es el número de elementos que ya se han eliminado.

Ejemplos:

Entrada: arr[] = {3, 1, 3, 2}
Salida: 25
Explicación: 
Primero elimine 3. Costo = 2^(0)*3 = 3 
Luego elimine 3. Costo = 2^(1)*3 = 6 
Luego elimine 2. Costo = 2^(2)*2 = 8 
Por último, elimine 1. Costo = 2^(3)*1 = 8 
Costo total = 3 + 6 + 8 + 8 = 25

Entrada: arr[] = {1, 2}
Salida: 4
Explicación: 
Primero elimine 2. Costo = 2^(0)*2 = 2 
Luego elimine 1. Costo = 2^(1)*1 = 2 
Costo total = 2 + 2 = 4

Enfoque:  La idea es utilizar un paradigma de programación codicioso para resolver este problema. Tenemos que minimizar la expresión ( 2^j * arr[i] ). Esto se puede hacer por: 

• Ordene la array en orden decreciente.
• Multiplique pow(2, i) con cada elemento i, comenzando desde 0 hasta el tamaño de la array.

Por lo tanto, el costo total de eliminar elementos de la array se da como: 

cuando la array está en orden decreciente.
 

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

// C++ implementation to find the
// minimum cost of removing all
// elements from the array
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
// Function to find the minimum
// cost of removing elements from
// the array
int removeElements(ll arr[], int n)
{
 
    // Sorting in Increasing order
    sort(arr, arr + n, greater<int>());
    ll ans = 0;
     
    // Loop to find the minimum
    // cost of removing elements
    for (int i = 0; i < n; i++) {
        ans += arr[i] * pow(2, i);
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int n = 4;
    ll arr[n] = { 3, 1, 2, 3 };
 
    // Function Call
    cout << removeElements(arr, n);
}

// Java implementation to find the
// minimum cost of removing all
// elements from the array
import java.util.*;
 
class GFG{
 
// Reverse array in decreasing order
static long[] reverse(long a[])
{
    int i, n = a.length;
    long t;
     
    for(i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
    return a;
}
 
// Function to find the minimum
// cost of removing elements from
// the array
static long removeElements(long arr[],
                           int n)
{
     
    // Sorting in Increasing order
    Arrays.sort(arr);
    arr = reverse(arr);
 
    long ans = 0;
 
    // Loop to find the minimum
    // cost of removing elements
    for(int i = 0; i < n; i++)
    {
        ans += arr[i] * Math.pow(2, i);
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 4;
    long arr[] = { 3, 1, 2, 3 };
 
    // Function call
    System.out.print(removeElements(arr, n));
}
}
 
// This code is contributed by amal kumar choubey

# Python3 implementation to find the
# minimum cost of removing all
# elements from the array
 
# Function to find the minimum
# cost of removing elements from
# the array
def removeElements(arr, n):
 
    # Sorting in Increasing order
    arr.sort(reverse = True)
    ans = 0
 
    # Loop to find the minimum
    # cost of removing elements
    for i in range(n):
        ans += arr[i] * pow(2, i)
 
    return ans
 
# Driver Code
if __name__ == "__main__":
     
    n = 4
    arr = [ 3, 1, 2, 3 ]
 
    # Function call
    print(removeElements(arr, n))
     
# This code is contributed by chitranayal

// C# implementation to find the
// minimum cost of removing all
// elements from the array
using System;
 
class GFG{
 
// Reverse array in decreasing order
static long[] reverse(long []a)
{
    int i, n = a.Length;
    long t;
     
    for(i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
    return a;
}
 
// Function to find the minimum
// cost of removing elements from
// the array
static long removeElements(long []arr,
                           int n)
{
     
    // Sorting in Increasing order
    Array.Sort(arr);
    arr = reverse(arr);
 
    long ans = 0;
 
    // Loop to find the minimum
    // cost of removing elements
    for(int i = 0; i < n; i++)
    {
        ans += (long)(arr[i] * Math.Pow(2, i));
    }
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 4;
    long []arr = { 3, 1, 2, 3 };
 
    // Function call
    Console.Write(removeElements(arr, n));
}
}
 
// This code is contributed by amal kumar choubey

<script>
      // JavaScript implementation to find the
      // minimum cost of removing all
      // elements from the array
      // Function to find the minimum
      // cost of removing elements from
      // the array
      function removeElements(arr, n) {
        // Sorting in Increasing order
        arr.sort((a, b) => b - a);
 
        var ans = 0;
 
        // Loop to find the minimum
        // cost of removing elements
        for (var i = 0; i < n; i++) {
          ans += arr[i] * Math.pow(2, i);
        }
        return ans;
      }
 
      // Driver Code
      var n = 4;
      var arr = [3, 1, 2, 3];
 
      // Function call
      document.write(removeElements(arr, n));
</script>

25

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