Given an array arr[] of N integers and an integer K, the task is to calculate the minimum cost by spilling the array elements into subsets of size K and adding the maximum ⌈K/2⌉ elements into the cost.
Note: ⌈K/2⌉ means ceiling value of K/2.
Examples:
Input: arr[] = {1, 1, 2, 2}, K = 2
Output: 3
Explanation: The given array elements can be divided into subsets {2, 2} and {1, 1}.
Hence, the cost will be 2 + 1 = 3, which is the minimum possible.Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Output: 16
Explanation: The array can be split like {1, 2, 3} and {4, 5, 6}.
Now ceil(3/2) = ceil(1.5) = 2.
So take 2 highest elements from each set.
The sum becomes 2 + 3 + 5 + 6 = 16
Approach: The given problem can be solved by using a greedy approach. The idea is to sort the elements in decreasing order and start forming the groups of K elements consecutively and maintain the sum of the highest ⌈K/2⌉ elements of each group in a variable. This will ensure that the elements whose cost is not considered are the maximum possible and therefore minimize the overall cost of the selected elements.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum cost by splitting// the array into subsets of size at most K// and adding maximum K/2 elements into costint minimizeCost(vector<int> arr, int K){ // Stores the final cost int ans = 0; // Sort the array arr[] sort(arr.begin(), arr.end(), greater<int>()); // Loop to iterate over each // group of K elements for (int i = 0; i < arr.size(); i += K) { // Loop to iterate over // maximum K/2 elements for (int j = i; j < i + ceil(K / 2.0) && j < arr.size(); j++) { ans += arr[j]; } } // Return Answer return ans;}// Driver codeint main(){ vector<int> arr = { 1, 2, 3, 4, 5, 6 }; int K = 3; cout << minimizeCost(arr, K); return 0;} |
Java
// JAVA program of the above approachimport java.util.*;class GFG { // Function to find minimum cost by splitting // the array into subsets of size at most K // and adding maximum K/2 elements into cost public static int minimizeCost(ArrayList<Integer> arr, int K) { // Stores the final cost int ans = 0; // Sort the array arr[] Collections.sort(arr, Collections.reverseOrder()); // Loop to iterate over each // group of K elements for (int i = 0; i < arr.size(); i += K) { // Loop to iterate over // maximum K/2 elements for (int j = i; j < i + Math.ceil(K / 2.0) && j < arr.size(); j++) { ans += arr.get(j); } } // Return Answer return ans; } // Driver code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>( Arrays.asList(1, 2, 3, 4, 5, 6)); int K = 3; System.out.print(minimizeCost(arr, K)); }}// This code is contributed by Taranpreet |
Python
# Python program of the above approachimport math# Function to find minimum cost by splitting# the array into subsets of size at most K# and adding maximum K/2 elements into costdef minimizeCost(arr, K): # Stores the final cost ans = 0 # Sort the array arr[] arr.sort(reverse = True) # Loop to iterate over each # group of K elements i = 0 while(i < len(arr)): # Loop to iterate over # maximum K/2 elements j = i while(j < i + math.ceil(K / 2.0) and j < len(arr)): ans += arr[j] j += 1 i += K # Return Answer return ans# Driver codearr = [ 1, 2, 3, 4, 5, 6 ]K = 3print(minimizeCost(arr, K))# This code is contributed by samim2000. |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find minimum cost by splitting // the array into subsets of size at most K // and adding maximum K/2 elements into cost static int minimizeCost(List<int> arr, int K) { // Stores the final cost int ans = 0; // Sort the array arr[] arr.Sort((a, b) => b - a); // Loop to iterate over each // group of K elements for (int i = 0; i < arr.Count; i += K) { // Loop to iterate over // maximum K/2 elements for (int j = i; j < i + Math.Ceiling(K / 2.0) && j < arr.Count; j++) { ans += arr[j]; } } // Return Answer return ans; } // Driver Code public static void Main() { List<int> arr = new List<int>{ 1, 2, 3, 4, 5, 6 }; int K = 3; Console.Write(minimizeCost(arr, K)); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Function to find minimum cost by splitting // the array into subsets of size at most K // and adding maximum K/2 elements into cost function minimizeCost(arr, K) { // Stores the final cost let ans = 0; // Sort the array arr[] arr.sort(function (a, b) { return b - a }) // Loop to iterate over each // group of K elements for (let i = 0; i < arr.length; i += K) { // Loop to iterate over // maximum K/2 elements for (let j = i; j < i + Math.ceil(K / 2.0) && j < arr.length; j++) { ans += arr[j]; } } // Return Answer return ans; } // Driver code let arr = [1, 2, 3, 4, 5, 6]; let K = 3; document.write(minimizeCost(arr, K)); // This code is contributed by Potta Lokesh </script> |
16
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
