Given an array arr[] consisting of N integers, the task is to find the minimum cost to remove all elements from the array such that the cost of removing any element is the absolute difference between the current time instant T (initially 1) and the array element arr[i] i.e., abs(T – arr[i]) where T.
Examples:
Input: arr[] = {3, 6, 4, 2}
Output: 0
Explanation:
T = 1: No removal
T = 2: Remove arr[3]. Cost = |2 – 2| = 0
T = 3: Remove arr[0]. Cost = |3 – 3| = 0
T = 4: Remove arr[2]. Cost = |4 – 4| = 0
T = 5: No removal.
T = 6: Remove arr[1]. Cost = |0| + |6 – 6| = 0
Therefore, the total cost = 0Input: arr[] = {4, 2, 4, 4, 5, 2}
Output: 4
Naive Approach: The idea is to use recursion to solve the problem. At each instant of time, two possibilities exists, either to remove any element or not. Therefore, to minimize the cost, sort the array. Then, starting from index 0 and time T = 1, solve the problem using following recurrence relation:
minCost(index, time) = min(minCost(index + 1, T + 1) + abs(time – a[index]), minCost(index, T + 1))
where, Base Case: If current index exceeds the current size of the array.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming as there are overlapping subproblems and overlapping substructure to the above recurrence relation. Follow the steps below to solve the problem:
- Initialize a 2-D array, cost[][] of size N*2N with some large value where cost[i][j] denotes the minimum cost to delete all the elements up to the ith index from the given array using j amount of time.
- Also, initialize cost[0][0] with 0 and variable, prev with 0 where prev will store the minimum of all previous cost values of the previous index.
- Traverse the given array arr[] using a variable i and then, for each i, iterate in the range [1, 2N] using variable j:
- If the value of (prev + abs(j – arr[i – 1]) is less than cost[i][j], then update cost[i][j] to this value.
- If cost[i – 1][j] is less than prev, then update prev to this value.
- After the above steps, print the minimum cost as cost[N][j].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define INF 10000// Function to find the minimum cost// to delete all array elementsvoid minCost(int arr[], int n){ // Sort the input array sort(arr, arr + n); // Store the maximum time to delete // the array in the worst case int m = 2 * n; // Store the result in cost[][] table int cost[n + 1][m + 1]; // Initialize the table cost[][] for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { cost[i][j] = INF; } } // Base Case cost[0][0] = 0; // Store the minimum of all cost // values of the previous index int prev = 0; // Iterate from range [1, n] // using variable i for (int i = 1; i <= n; i++) { // Update prev prev = cost[i - 1][0]; // Iterate from range [1, m] // using variable j for (int j = 1; j <= m; j++) { // Update cost[i][j] cost[i][j] = min(cost[i][j], prev + abs(j - arr[i - 1])); // Update the prev prev = min(prev, cost[i - 1][j]); } } // Store the minimum cost to // delete all elements int minCost = INF; // Find the minimum of all values // of cost[n][j] for (int j = 1; j <= m; j++) { minCost = min(minCost, cost[n][j]); } // Print minimum cost cout << minCost;}// Driver Codeint main(){ int arr[] = { 4, 2, 4, 4, 5, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call minCost(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;import java.io.*; class GFG{ static int INF = 10000; // Function to find the minimum cost// to delete all array elementsstatic void minCost(int arr[], int n){ // Sort the input array Arrays.sort(arr); // Store the maximum time to delete // the array in the worst case int m = 2 * n; // Store the result in cost[][] table int cost[][] = new int[n + 1][m + 1]; // Initialize the table cost[][] for(int i = 0; i <= n; i++) { for(int j = 0; j <= m; j++) { cost[i][j] = INF; } } // Base Case cost[0][0] = 0; // Store the minimum of all cost // values of the previous index int prev = 0; // Iterate from range [1, n] // using variable i for(int i = 1; i <= n; i++) { // Update prev prev = cost[i - 1][0]; // Iterate from range [1, m] // using variable j for(int j = 1; j <= m; j++) { // Update cost[i][j] cost[i][j] = Math.min(cost[i][j], prev + Math.abs( j - arr[i - 1])); // Update the prev prev = Math.min(prev, cost[i - 1][j]); } } // Store the minimum cost to // delete all elements int minCost = INF; // Find the minimum of all values // of cost[n][j] for(int j = 1; j <= m; j++) { minCost = Math.min(minCost, cost[n][j]); } // Print minimum cost System.out.print(minCost);} // Driver Codepublic static void main(String[] args){ int arr[] = { 4, 2, 4, 4, 5, 2 }; int N = arr.length; // Function Call minCost(arr, N);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approachINF = 10000# Function to find the minimum cost# to delete all array elementsdef minCost(arr, n): # Sort the input array arr = sorted(arr) # Store the maximum time to delete # the array in the worst case m = 2 * n # Store the result in cost[][] table cost = [[INF for i in range(m + 1)] for i in range(n + 1)] # Base Case cost[0][0] = 0 # Store the minimum of all cost # values of the previous index prev = 0 # Iterate from range [1, n] # using variable i for i in range(1, n + 1): # Update prev prev = cost[i - 1][0] # Iterate from range [1, m] # using variable j for j in range(1, m + 1): # Update cost[i][j] cost[i][j] = min(cost[i][j], prev + abs(j - arr[i - 1])) # Update the prev prev = min(prev, cost[i - 1][j]) # Store the minimum cost to # delete all elements minCost = INF # Find the minimum of all values # of cost[n][j] for j in range(1, m + 1): minCost = min(minCost, cost[n][j]) # Print minimum cost print(minCost)# Driver Codeif __name__ == '__main__': arr=[4, 2, 4, 4, 5, 2] N = len(arr) # Function Call minCost(arr, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ static int INF = 10000; // Function to find the minimum cost// to delete all array elementsstatic void minCost(int[] arr, int n){ // Sort the input array Array.Sort(arr); // Store the maximum time to delete // the array in the worst case int m = 2 * n; // Store the result in cost[][] table int[,] cost = new int[n + 1, m + 1]; // Initialize the table cost[][] for(int i = 0; i <= n; i++) { for(int j = 0; j <= m; j++) { cost[i, j] = INF; } } // Base Case cost[0, 0] = 0; // Store the minimum of all cost // values of the previous index int prev = 0; // Iterate from range [1, n] // using variable i for(int i = 1; i <= n; i++) { // Update prev prev = cost[i - 1, 0]; // Iterate from range [1, m] // using variable j for(int j = 1; j <= m; j++) { // Update cost[i][j] cost[i, j] = Math.Min(cost[i, j], prev + Math.Abs( j - arr[i - 1])); // Update the prev prev = Math.Min(prev, cost[i - 1, j]); } } // Store the minimum cost to // delete all elements int minCost = INF; // Find the minimum of all values // of cost[n][j] for(int j = 1; j <= m; j++) { minCost = Math.Min(minCost, cost[n, j]); } // Print minimum cost Console.Write(minCost);}// Driver Codepublic static void Main(){ int[] arr = { 4, 2, 4, 4, 5, 2 }; int N = arr.Length; // Function Call minCost(arr, N);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// JavaScript program for above approachlet INF = 10000;// Function to find the minimum cost// to delete all array elementsfunction minCost(arr, n){ // Sort the input array arr.sort(); // Store the maximum time to delete // the array in the worst case let m = 2 * n; // Store the result in cost[][] table let cost = new Array(n + 1); // Loop to create 2D array using 1D array for (var i = 0; i < cost.length; i++) { cost[i] = new Array(2); } // Initialize the table cost[][] for(let i = 0; i <= n; i++) { for(let j = 0; j <= m; j++) { cost[i][j] = INF; } } // Base Case cost[0][0] = 0; // Store the minimum of all cost // values of the previous index let prev = 0; // Iterate from range [1, n] // using variable i for(let i = 1; i <= n; i++) { // Update prev prev = cost[i - 1][0]; // Iterate from range [1, m] // using variable j for(let j = 1; j <= m; j++) { // Update cost[i][j] cost[i][j] = Math.min(cost[i][j], prev + Math.abs( j - arr[i - 1])); // Update the prev prev = Math.min(prev, cost[i - 1][j]); } } // Store the minimum cost to // delete all elements let minCost = INF; // Find the minimum of all values // of cost[n][j] for(let j = 1; j <= m; j++) { minCost = Math.min(minCost, cost[n][j]); } // Print minimum cost document.write(minCost);}// Driver Code let arr = [ 4, 2, 4, 4, 5, 2 ]; let N = arr.length; // Function Call minCost(arr, N);// This code is contributed by avijitmondal1998.</script> |
Output:
4
Time Complexity: O(N2)
Auxiliary Space: O(N2)
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!
