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 = 25Input: 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}](https://neveropen.co.za/wp-content/uploads/2023/10/wardslaus_rubhabha_quicklatex.com-bb9d2e1b535d12c88184c0d2a3a343f2_l3.png "Rendered by QuickLaTeX.com")
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 arrayint 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 Codeint 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 arrayimport java.util.*;class GFG{// Reverse array in decreasing orderstatic 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 arraystatic 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 Codepublic 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 arraydef 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 Codeif __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 arrayusing System;class GFG{// Reverse array in decreasing orderstatic 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 arraystatic 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 Codepublic 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
25
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!