Maximize sum of means of two subsets formed by dividing given Array into them
Given an array arr[] of size N, the task is to find the maximum sum of means of 2 non-empty subsets of the given array such that each element is part of one of the subsets.
Examples:
Input: N = 2, arr[] = {1, 3}
Output: 4.00
Explanation: Since there are only two elements, make two subsets as {1} and {3}.
Their sizes are 1 so mean for both will be 1.00 and 3.00 which sums to 4.00Input: N = 5, arr[] = {1, 2, 3, 4, 5}
Output: 7.50
Explanation: Since there are 5 elements in the array, divide the array as {1, 2, 3, 4} and {5}.
Their sizes are 4 and 1 respectively. The mean for the first subset will be (1+2+3+4)/4 = 2.50
and the mean of the other subset will be 5. Hence the sum of means will be 2.50+5.00 = 7.50
For any other subset division the sum of means will not be more than 7.50.
Examples: {1, 2, 3} and {4, 5} the means will be (1+2+3)/3 and (4+5)/2
which is 2.00 and 4.50 respectively which sums to 6.50 which is less than 7.50
Approach: The task can be solved using some observations It can be observed that the maximum sum of means of 2 non-empty subsets can be achieved if one of the subsets contains only the maximum element & the other subset contains the rest of the elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum sum of the // mean of the sum of two subsets of an array double maxMeanSubsetSum( int arr[], int N) { // Sorting the array sort(arr, arr + N); // Stores the sum of array double sum = 0; // Loop through the array and store // sum of elements except the largest for ( int i = 0; i < N - 1; i++) { sum += arr[i]; } // Calculating the mean sum = sum / (N - 1); // Adding the largest number // to the calculated mean sum += arr[N - 1]; return sum; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int N = 5; // Giving output correct to // two decimal places cout << setprecision(2) << fixed << maxMeanSubsetSum(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to return the maximum sum of the // mean of the sum of two subsets of an array static double maxMeanSubsetSum( int arr[], int N) { // Sorting the array Arrays.sort(arr); // Stores the sum of array double sum = 0 ; // Loop through the array and store // sum of elements except the largest for ( int i = 0 ; i < N - 1 ; i++) { sum += arr[i]; } // Calculating the mean sum = sum / (N - 1 ); // Adding the largest number // to the calculated mean sum += arr[N - 1 ]; return sum; } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int N = 5 ; // Giving output correct to // two decimal places System.out.print(String.format( "%.2f" , maxMeanSubsetSum(arr, N))); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach # Function to return the maximum sum of the # mean of the sum of two subsets of an array def maxMeanSubsetSum(arr, N): # Sorting the array arr.sort() # Stores the sum of array sum = 0 # Loop through the array and store # sum of elements except the largest for i in range (N - 1 ): sum + = arr[i] # Calculating the mean sum = sum / (N - 1 ) # Adding the largest number # to the calculated mean sum = sum + arr[N - 1 ] return sum # Driver code arr = [ 1 , 2 , 3 , 4 , 5 ] N = 5 # Giving output correct to # two decimal places print ( "{0:.2f}" . format (maxMeanSubsetSum(arr, N))) # This code is contributed by Potta Lokesh |
C#
// C# program for the above approach using System; public class GFG { // Function to return the maximum sum of the // mean of the sum of two subsets of an array static double maxMeanSubsetSum( int [] arr, int N) { // Sorting the array Array.Sort(arr); // Stores the sum of array double sum = 0; // Loop through the array and store // sum of elements except the largest for ( int i = 0; i < N - 1; i++) { sum += arr[i]; } // Calculating the mean sum = sum / (N - 1); // Adding the largest number // to the calculated mean sum += arr[N - 1]; return sum; } // Driver Code public static void Main(String[] args) { int [] arr = { 1, 2, 3, 4, 5 }; int N = 5; // Giving output correct to // two decimal places Console.Write( string .Format( "{0:0.00}" , maxMeanSubsetSum(arr, N))); } } // This code is contributed by code_hunt. |
Javascript
<script> // JavaScript program for the above approach // Function to return the maximum sum of the // mean of the sum of two subsets of an array const maxMeanSubsetSum = (arr, N) => { // Sorting the array arr.sort(); // Stores the sum of array let sum = 0; // Loop through the array and store // sum of elements except the largest for (let i = 0; i < N - 1; i++) { sum += arr[i]; } // Calculating the mean sum = sum / (N - 1); // Adding the largest number // to the calculated mean sum += arr[N - 1]; return sum; } // Driver code let arr = [1, 2, 3, 4, 5]; let N = 5; // Giving output correct to // two decimal places document.write(parseFloat(maxMeanSubsetSum(arr, N)).toFixed(2)); // This code is contributed by rakeshsahni </script> |
7.50
Time Complexity: O(N * logN)
Auxiliary Space: O(1)