Given an array arr[] of size N and an integer K. The task is to find the minimum cost required to collect the sum of the array. The sum of the array is collected by picking any element and adding it to an element of any index in the array. The addition of elements at the same index is allowed for at most K times.
Example:
Input: arr[] = {3, 6, 4, 1, 1}, N = 5, K = 2
Output: 11
Explanation: Sum of the array can be collected as follows:
- Pick element at index 4 and add it to element at index 2 i.e (1 ⇢ 4) = 1+4 = 5, cost = 1 and arr[] = {3, 6, 5, 1, 0}.
- Pick element at index 3 and add it to element at index 2 i.e (1 ⇢ 5) = 1+5 = 6, cost = 1+1 = 2 and arr[] = {3, 6, 6, 0, 0}.
- Pick element at index 0 and add it to element at index 1 i.e (3 ⇢ 6) = 3+6 = 9, cost = 2+3 = 5 and arr[] = {0, 9, 6, 0, 0}.
- Pick element at index 2 and add it to element at index 1 i.e (6 ⇢ 9) = 6+9 = 15, cost = 5+6 = 11 and arr[] = {0, 15, 0, 0, 0}.
Input: arr[] = {5, 3, 2, 1, 4, 6}, N = 6, K = 3
Output: 18
Explanation: Sum can be collected as follows
- Pick element at index 3 and add it to element at index 4 i.e (1 ⇢ 4) = 1+4 = 5, cost = 1 and arr[] = {5, 3, 2, 0, 5, 6}.
- Pick element at index 2 and add it to element at index 0 i.e (2 ⇢ 5) = 2+5 = 7, cost = 1+2 = 3 and arr[] = {7, 3, 0, 0, 5, 6}.
- Pick element at index 1 and add it to element at index 5 i.e (3 ⇢ 6) = 3+6 = 9, cost = 3+3 = 6 and arr[] = {7, 0, 0, 0, 5, 9}.
- Pick element at index 4 and add it to element at index 5 i.e (5 ⇢ 9) = 5+9 = 14, cost = 6+5 = 11 and arr[] = {7, 0, 0, 0, 0, 14}.
- Pick element at index 0 and add it to element at index 5 i.e (7 ⇢ 14) = 7+14 = 21, cost = 11+7 = 18 and arr[] = {0, 0, 0, 0, 0, 21}.
Approach: The given problem can be solved using a greedy approach. The idea is to sort the array. following interpretation of the problem: given elements are the graph vertices. Operation ⇢ add one element to other ⇢ changes to operation of suspension of sub-tree of one vertices to another.
The task is to get such tree configuration, that each vertices has no more than K sub-trees suspended to it, and sum of the products of numbers, written on vertices, and vertices’ depth (where root’s depth is 0) is minimal. In order to minimize the sum:
- vertices with a larger number must not have more depth than vertices with smaller number (otherwise it’s possible to change them and to get less sum).
- each inner vertices, besides, maybe, one, has exactly k successors. (In actual implementation, there is no need to build a tree, we only need to know that this is a tree.)
Now calculate the sum for this configuration. In order do to it, follow the following steps:
- Add to answer sum of elements from 1st to kth (in 0-indexed array, sorted in non-increasing order), multiplied by 1; then sum of sizes of next k piles, multiplied by 2; and so on till the end of array.
- To get the answer about the sum of segment, use prefix sum after sorting the array.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to return the difference // of the elements in a range int sum( int s[], int l, int r, int N) { r = min(r, (N - 1)); return s[r] - s[l - 1]; } // Function to find the minimum cost required // to collect the sum of the array int minCost( int arr[], int K, int N) { int s[N]; // Sort the array in descending order sort(arr, arr + N, greater< int >()); s[0] = arr[0]; // Traverse and store the sums // in prefix array s[] for ( int i = 1; i < N; i++) s[i] = s[i - 1] + arr[i]; int res_1 = 0; // Iterate the array and add the // value of the element // multiplied by its index for ( int i = 1; i < N; i++) res_1 += arr[i] * i; // If K = 1 return res_1 if (K == 1) return res_1; // Variable to store the answer int res = 0, sz = 1; // Traverse and find the // answer accordingly for ( int j = 1, t = 1; j < N; j += sz, t++) { sz *= K; res += sum(s, j, j + sz - 1, N) * t; } // Return res return res; } // Driver Code int main() { // Initialize the array int arr[] = { 3, 6, 4, 1, 1 }; int K = 2; int N = sizeof (arr) / sizeof (arr[0]); // Call the function and // print the answer cout << minCost(arr, K, N); return 0; } |
Java
// Java code for the above approach import java.util.Arrays; import java.util.Collections; class GFG { // Function to return the difference // of the elements in a range static int sum( int s[], int l, int r, int N) { r = Math.min(r, (N - 1 )); return s[r] - s[l - 1 ]; } // Function to find the minimum cost required // to collect the sum of the array static int minCost( int arr[], int K, int N) { int [] s = new int [N]; // Sort the array in descending order // Sorting the array in ascending order Arrays.sort(arr); // Reversing the array reverse(arr); s[ 0 ] = arr[ 0 ]; // Traverse and store the sums // in prefix array s[] for ( int i = 1 ; i < N; i++) s[i] = s[i - 1 ] + arr[i]; int res_1 = 0 ; // Iterate the array and add the // value of the element // multiplied by its index for ( int i = 1 ; i < N; i++) res_1 += arr[i] * i; // If K = 1 return res_1 if (K == 1 ) return res_1; // Variable to store the answer int res = 0 , sz = 1 ; // Traverse and find the // answer accordingly for ( int j = 1 , t = 1 ; j < N; j += sz, t++) { sz *= K; res += sum(s, j, j + sz - 1 , N) * t; } // Return res return res; } public static void reverse( int [] array) { // Length of the array int n = array.length; // Swapping the first half elements with last half // elements for ( int i = 0 ; i < n / 2 ; i++) { // Storing the first half elements temporarily int temp = array[i]; // Assigning the first half to the last half array[i] = array[n - i - 1 ]; // Assigning the last half to the first half array[n - i - 1 ] = temp; } } // Driver Code public static void main(String[] args) { // Initialize the array int arr[] = { 3 , 6 , 4 , 1 , 1 }; int K = 2 ; int N = arr.length; // Call the function and // print the answer System.out.println(minCost(arr, K, N)); } } // This code is contributed by Potta Lokesh |
Python3
# Python implementation for the above approach # Function to return the difference # of the elements in a range def sum (s, l, r, N): r = min (r, (N - 1 )) return s[r] - s[l - 1 ] # Function to find the minimum cost required # to collect the sum of the array def minCost (arr, K, N): s = [ 0 ] * N # Sort the array in descending order arr = sorted (arr, reverse = True ) s[ 0 ] = arr[ 0 ] # Traverse and store the sums # in prefix array s[] for i in range ( 1 , N): s[i] = s[i - 1 ] + arr[i] res_1 = 0 # Iterate the array and add the # value of the element # multiplied by its index for i in range ( 1 , N): res_1 + = arr[i] * i # If K = 1 return res_1 if (K = = 1 ): return res_1 # Variable to store the answer res = 0 sz = 1 # Traverse and find the # answer accordingly j = 1 t = 1 while (j < N ): sz * = K res + = sum (s, j, j + sz - 1 , N) * t j + = sz t + = 1 # Return res return res # Driver Code # Initialize the array arr = [ 3 , 6 , 4 , 1 , 1 ] K = 2 N = len (arr) # Call the function and # print the answer print (minCost(arr, K, N)) # This code is contributed by Saurabh Jaiswal |
C#
// C# code for the above approach using System; public class GFG { // Function to return the difference // of the elements in a range static int sum( int []s, int l, int r, int N) { r = Math.Min(r, (N - 1)); return s[r] - s[l - 1]; } // Function to find the minimum cost required // to collect the sum of the array static int minCost( int []arr, int K, int N) { int [] s = new int [N]; // Sort the array in descending order // Sorting the array in ascending order Array.Sort(arr); // Reversing the array reverse(arr); s[0] = arr[0]; // Traverse and store the sums // in prefix array s[] for ( int i = 1; i < N; i++) s[i] = s[i - 1] + arr[i]; int res_1 = 0; // Iterate the array and add the // value of the element // multiplied by its index for ( int i = 1; i < N; i++) res_1 += arr[i] * i; // If K = 1 return res_1 if (K == 1) return res_1; // Variable to store the answer int res = 0, sz = 1; // Traverse and find the // answer accordingly for ( int j = 1, t = 1; j < N; j += sz, t++) { sz *= K; res += sum(s, j, j + sz - 1, N) * t; } // Return res return res; } public static void reverse( int [] array) { // Length of the array int n = array.Length; // Swapping the first half elements with last half // elements for ( int i = 0; i < n / 2; i++) { // Storing the first half elements temporarily int temp = array[i]; // Assigning the first half to the last half array[i] = array[n - i - 1]; // Assigning the last half to the first half array[n - i - 1] = temp; } } // Driver Code public static void Main(String[] args) { // Initialize the array int []arr = { 3, 6, 4, 1, 1 }; int K = 2; int N = arr.Length; // Call the function and // print the answer Console.WriteLine(minCost(arr, K, N)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation for the above approach // Function to return the difference // of the elements in a range const sum = (s, l, r, N) => { r = Math.min(r, (N - 1)); return s[r] - s[l - 1]; } // Function to find the minimum cost required // to collect the sum of the array const minCost = (arr, K, N) => { let s = new Array(N).fill(0); // Sort the array in descending order arr.sort((a, b) => b - a); s[0] = arr[0]; // Traverse and store the sums // in prefix array s[] for (let i = 1; i < N; i++) s[i] = s[i - 1] + arr[i]; let res_1 = 0; // Iterate the array and add the // value of the element // multiplied by its index for (let i = 1; i < N; i++) res_1 += arr[i] * i; // If K = 1 return res_1 if (K == 1) return res_1; // Variable to store the answer let res = 0, sz = 1; // Traverse and find the // answer accordingly for (let j = 1, t = 1; j < N; j += sz, t++) { sz *= K; res += sum(s, j, j + sz - 1, N) * t; } // Return res return res; } // Driver Code // Initialize the array let arr = [3, 6, 4, 1, 1]; let K = 2; let N = arr.length // Call the function and // print the answer document.write(minCost(arr, K, N)); // This code is contributed by rakeshsahni </script> |
11
Time Complexity: O(N* log N)
Auxiliary Space: O(N)