Minimize cost to reduce Array if for choosing every 2 elements, 3rd one is chosen for free
Given an array arr[]. The task is to minimize the cost of reducing the array with a given operation. In one operation choose two elements add their value to the total cost and remove them and remove any other element with a value almost the two chosen elements.
Examples:
Input: arr[] = {1, 2, 3}
Output: 5
Explanation: Choose 2 and 3, cost = 5. 1 is reduced from array for free.Input: arr[] = {6, 5, 7, 9, 2, 2}
Output: 23
Approach: This problem can be solved by using the Greedy Approach. Follow the steps below to solve the given problem.
- Sort the given array.
- Traverse the sorted array from the end.
- Add 2 elements to the final cost and skip the 3rd one.
- Return the final cost.
Below is the implementation of the above approach.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum cost // to get the desired array int minCost(vector< int >& arr) { // Sorting the array sort(arr.begin(), arr.end()); int ans = 0; for ( int i = arr.size() - 1, k = 1; i >= 0; i--, k++) if (k == 3) k = 0; else ans += arr[i]; return ans; } // Driver Code int main() { vector< int > arr = { 6, 5, 7, 9, 2, 2 }; // Function Call cout << minCost(arr); return 0; } |
Java
// JAVA program for above approach import java.util.*; class GFG { // Function to find minimum cost // to get the desired array public static int minCost(ArrayList<Integer> arr) { // Sorting the array Collections.sort(arr); int ans = 0 ; for ( int i = arr.size() - 1 , k = 1 ; i >= 0 ; i--, k++) if (k == 3 ) k = 0 ; else ans += arr.get(i); return ans; } // Driver Code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>( Arrays.asList( 6 , 5 , 7 , 9 , 2 , 2 )); // Function Call System.out.print(minCost(arr)); } } // This code is contributed by Taranpreet |
Python3
# Python code for the above approach # Function to find minimum cost # to get the desired array def minCost(arr): # Sorting the array arr.sort() ans = 0 k = 1 for i in range ( len (arr) - 1 , 0 , - 1 ): if k = = 3 : k = 0 else : ans = ans + arr[i] k = k + 1 return ans # Driver Code arr = [ 6 , 5 , 7 , 9 , 2 , 2 ] # Function Call print (minCost(arr)) # This code is contributed by Potta Lokesh |
C#
// C# program for above approach using System; class GFG { // Function to find minimum cost // to get the desired array static int minCost( int [] arr) { // Sorting the array Array.Sort(arr); int ans = 0; for ( int i = arr.Length - 1, k = 1; i >= 0; i--, k++) if (k == 3) k = 0; else ans += arr[i]; return ans; } // Driver Code public static void Main() { int [] arr = { 6, 5, 7, 9, 2, 2 }; // Function Call Console.Write(minCost(arr)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for above approach // Function to find minimum cost // to get the desired array const minCost = (arr) => { // Sorting the array arr.sort(); let ans = 0; for (let i = arr.length - 1, k = 1; i >= 0; i--, k++) if (k == 3) k = 0; else ans += arr[i]; return ans; } // Driver Code let arr = [6, 5, 7, 9, 2, 2]; // Function Call document.write(minCost(arr)); // This code is contributed by rakeshsahni </script> |
Output
23
Time Complexity: O(N*log N)
Auxiliary Space: O(1)