Given an array arr[] of size N and a positive integer K, the task is to find the minimum possible cost to split the array into K subsets, where the cost of ith element ( 1-based indexing ) of each subset is equal to the product of that element and i.
Examples:
Input: arr[] = { 2, 3, 4, 1 }, K = 3
Output: 11
Explanation:
Split the array arr[] into K(= 3) subsets { { 4, 1 }, { 2 }, { 3 } }
Total cost of 1st subset = 4 * 1 + 1 * 2 = 6
Total cost of 2nd subset = 2 * 1 = 2
Total cost of 3rd subset = 3 * 1 = 3
Therefore, the total cost of K(= 3) subsets is 6 + 2 + 3 = 11.Input: arr[] = { 9, 20, 7, 8 }, K=2
Output: 59
Explanation:
Dividing the array arr[] into K(= 3) subsets { { 20, 8 }, { 9, 7 } }
Total cost of 1st subset = 20 * 1 + 8 * 2 = 36
Total cost of 2nd subset = 9 * 1 + 7 * 2 = 23
Therefore, the total cost of K(= 3) subsets is 36 + 23 = 59
Approach: The problem can be solved using Greedy technique. The idea is to divide the array elements such all elements in respective subsets is in decreasing order. Follow the steps below to solve the problem:
- Sort the given array in descending order.
- Initialize a variable, say totalCost, to store the minimum cost to split the array into K subsets.
- Initialize a variable, say X, to store the position of an element in a subset.
- Iterate over the range [1, N] using variable i. For every ith operation, increment the value of totalCost by ((arr[i]+ …+ arr[i + K]) * X) and update i = i + K, X += 1.
- Finally, print the value of totalCost.
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 minimum cost to// split array into K subsetsint getMinCost(int* arr, int n, int k){ // Sort the array in descending order sort(arr, arr + n, greater<int>()); // Stores minimum cost to split // the array into K subsets int min_cost = 0; // Stores position of // elements of a subset int X = 0; // Iterate over the range [1, N] for (int i = 0; i < n; i += k) { // Calculate the cost to select // X-th element of every subset for (int j = i; j < i + k && j < n; j++) { // Update min_cost min_cost += arr[j] * (X + 1); } // Update X X++; } return min_cost;}// Driver Codeint main(){ int arr[] = { 9, 20, 7, 8 }; int K = 2; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << getMinCost(arr, N, K) << endl;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{// reverses an arraystatic void reverse(int a[], int n) { int i, k, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } } // Function to find the minimum cost to// split array into K subsetsstatic int getMinCost(int[] arr, int n, int k){ // Sort the array in descending order Arrays.sort(arr); reverse(arr, n); // Stores minimum cost to split // the array into K subsets int min_cost = 0; // Stores position of // elements of a subset int X = 0; // Iterate over the range [1, N] for (int i = 0; i < n; i += k) { // Calculate the cost to select // X-th element of every subset for (int j = i; j < i + k && j < n; j++) { // Update min_cost min_cost += arr[j] * (X + 1); } // Update X X++; } return min_cost;} // Driver codepublic static void main(String[] args){ int arr[] = { 9, 20, 7, 8 }; int K = 2; int N = arr.length; // Function call System.out.println( getMinCost(arr, N, K));}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python program to implement# the above approach# Function to find the minimum cost to# split array into K subsetsdef getMinCost(arr, n, k): # Sort the array in descending order arr.sort(reverse = True) # Stores minimum cost to split # the array into K subsets min_cost = 0; # Stores position of # elements of a subset X = 0; # Iterate over the range [1, N] for i in range(0, n, k): # Calculate the cost to select # X-th element of every subset for j in range(i, n, 1): # Update min_cost if(j < i + k): min_cost += arr[j] * (X + 1); # Update X X += 1; return min_cost;# Driver codeif __name__ == '__main__': arr = [9, 20, 7, 8]; K = 2; N = len(arr); # Function call print(getMinCost(arr, N, K));# This code is contributed by 29AjayKumar |
C#
// C# program to implement // the above approach using System;class GFG{// reverses an arraystatic void reverse(int []a, int n) { int i, k, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } } // Function to find the minimum cost to// split array into K subsetsstatic int getMinCost(int[] arr, int n, int k){ // Sort the array in descending order Array.Sort(arr); reverse(arr, n); // Stores minimum cost to split // the array into K subsets int min_cost = 0; // Stores position of // elements of a subset int X = 0; // Iterate over the range [1, N] for (int i = 0; i < n; i += k) { // Calculate the cost to select // X-th element of every subset for (int j = i; j < i + k && j < n; j++) { // Update min_cost min_cost += arr[j] * (X + 1); } // Update X X++; } return min_cost;} // Driver codepublic static void Main(String[] args){ int []arr = { 9, 20, 7, 8 }; int K = 2; int N = arr.Length; // Function call Console.WriteLine( getMinCost(arr, N, K));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program to implement// the above approach// Reverses an arrayfunction reverse(a, n) { var i, k, t; for(i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; }}// Function to find the minimum cost to// split array into K subsetsfunction getMinCost(arr, n, k){ // Sort the array in descending order arr.sort((a, b) => b - a); // Stores minimum cost to split // the array into K subsets var min_cost = 0; // Stores position of // elements of a subset var X = 0; // Iterate over the range [1, N] for(var i = 0; i < n; i += k) { // Calculate the cost to select // X-th element of every subset for(var j = i; j < i + k && j < n; j++) { // Update min_cost min_cost += arr[j] * (X + 1); } // Update X X++; } return min_cost;}// Driver codevar arr = [ 9, 20, 7, 8 ];var K = 2;var N = arr.length;// Function calldocument.write(getMinCost(arr, N, K));// This code is contributed by rdtank</script> |
Output:
59
Time Complexity: O(N * log(N))
Auxiliary Space: O(1) it is using constant space for variables
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!
