Minimum cost to empty Array where cost of removing an element is 2^(removed_count) * arr[i]

0 0 4 minutes read

Given an array arr[], the task is to find the minimum cost to remove all elements from the array where the cost of removing an element is 2^j * arr[i]. Here, j is the number of elements that have already been removed.

Examples:

Input: arr[] = {3, 1, 3, 2}
Output: 25
Explanation:
First remove 3. Cost = 2^(0)*3 = 3
Then remove 3. Cost = 2^(1)*3 = 6
Then remove 2. Cost = 2^(2)*2 = 8
At last, remove 1. Cost = 2^(3)*1 = 8
Total Cost = 3 + 6 + 8 + 8 = 25

Input: arr[] = {1, 2}
Output: 4
Explanation:
First remove 2. Cost = 2^(0)*2 = 2
Then remove 1. Cost = 2^(1)*1 = 2
Total Cost = 2 + 2 = 4

Approach: The idea is to use a greedy programming paradigm to solve this problem.
We have to minimize the expression ( 2^j * arr[i] ). This can be done by:

Sort the Array in Decreasing order.
Multiply pow(2, i) with every element i, starting from 0 to the size of the array.

Therefore, the total cost of removing elements from the array is given as:

$\text{Total Cost = }arr[0]*2^{0} + arr[1] * 2^{1} + .... arr[n]*2^{n}$

when the array is in decreasing order.

Below is the implementation of the above approach:

C++

// 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

// 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

# 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#

// 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

Javascript

<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>

Output

Time Complexity: O(N * log N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!