Maximize cost to empty given array by repetitively removing K array elements
Given an array, arr[] of size N and an integer K ( N % K = 0), the task is find the maximum cost to remove all the array elements. In each operation, exactly K array elements can be removed and the cost of removal is equal to the second smallest element removed.
Examples:
Input: arr[] = { 1, 3, 4, 1, 5, 1, 5, 3 }, K = 4
Output: 5
Explanation:
Removing {arr[0], arr[3], arr[5], arr[7]} modifies arr[] to {3, 4, 5, 5}. Second smallest element removed = 1. Therefore, cost = 1
Removing {arr[0], arr[1], arr[2], arr[3]} modifies arr[] to {}. Second smallest element removed = 4. Therefore, cost = 1 + 4 = 5
Therefore, the required output is = 5Input: arr[] = { 1, 2, 3, 4}, K = 4
Output: 2
Approach: The problem can be solved using greedy technique. The idea is to sort the array and repetitively remove the smallest array elements at each operation. Follow the steps below to solve the problem:
- Initialize a variable, say maxCost, to store the maximum cost to remove all the array elements.
- Sort the array in ascending order.
- Traverse the array using variable i and update the value of maxCost = arr[i + 1] and i = i + K.
- Finally, print the value of maxCost.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum cost to // remove all array elements int maxCostToRemove( int arr[], int N, int K) { // Stores maximum cost to // remove array elements int maxCost = 0; // Sort array in // ascending order sort(arr, arr + N); // Traverse the array for ( int i = 0; i < N; i += K) { // Update maxCost maxCost += arr[i + 1]; } return maxCost; } // Driver Code int main() { int arr[]= { 1, 3, 4, 1, 5, 1, 5, 3}; int N = sizeof (arr) / sizeof (arr[0]); int K = 4; cout<< maxCostToRemove(arr, N, K); } |
Java
// Java program for the above approach import java.io.*; import java.util.Arrays; class GFG{ // Function to find the maximum cost to // remove all array elements static int maxCostToRemove( int arr[], int N, int K) { // Stores maximum cost to // remove array elements int maxCost = 0 ; // Sort array in // ascending order Arrays.sort(arr); // Traverse the array for ( int i = 0 ; i < N; i += K) { // Update maxCost maxCost += arr[i + 1 ]; } return maxCost; } // Drive Code public static void main(String[] args) { int arr[]= { 1 , 3 , 4 , 1 , 5 , 1 , 5 , 3 }; int N = arr.length; int K = 4 ; System.out.print(maxCostToRemove(arr, N, K)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program to implement # the above approach # Function to find the maximum cost to # remove all array elements def maxCostToRemove(arr, N, K): # Stores maximum cost to # remove array elements maxCost = 0 # Sort array in # ascending order arr = sorted (arr) # Traverse the array for i in range ( 0 , N, K): # Update maxCost maxCost + = arr[i + 1 ] return maxCost # Driver Code if __name__ = = '__main__' : arr = [ 1 , 3 , 4 , 1 , 5 , 1 , 5 , 3 ] N = len (arr) K = 4 print (maxCostToRemove(arr, N, K)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum cost to // remove all array elements static int maxCostToRemove( int []arr, int N, int K) { // Stores maximum cost to // remove array elements int maxCost = 0; // Sort array in // ascending order Array.Sort(arr); // Traverse the array for ( int i = 0; i < N; i += K) { // Update maxCost maxCost += arr[i + 1]; } return maxCost; } // Drive Code public static void Main(String[] args) { int []arr= { 1, 3, 4, 1, 5, 1, 5, 3}; int N = arr.Length; int K = 4; Console.Write(maxCostToRemove(arr, N, K)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the maximum cost to // remove all array elements function maxCostToRemove(arr, N, K) { // Stores maximum cost to // remove array elements let maxCost = 0; // Sort array in // ascending order arr.sort(); // Traverse the array for (let i = 0; i < N; i += K) { // Update maxCost maxCost += arr[i + 1]; } return maxCost; } // Driver code let arr = [ 1, 3, 4, 1, 5, 1, 5, 3 ]; let N = arr.length; let K = 4; document.write(maxCostToRemove(arr, N, K)); // This code is contributed by code_hunt </script> |
5
Time Complexity: O(N * log N)
Auxiliary Space O(1)
Contact Us