Given an array A[] consisting of N integers and two integers X and Y, the task is to find the maximum sum of the averages of each subsequences obtained by splitting the array into subsequences of lengths lying in the range [X, Y].
Note: The values of X and Y are such that it is always possible to make such groups.
Examples:
Input: A[] = {4, 10, 6, 5}, X = 2, Y = 3
Output: 12.50
Explanation:
Divide the given array into two groups as {4, 10}, {6, 5} such that their sizes lies over the range [2, 3].
The average of the first group = (4 + 10) / 2 = 7.
The average of the second group = (6 + 5) / 2 = 5.5.
Therefore, the sum of average = 7 + 5.5 = 12.5, which is minimum among all possible groups.Input: A[] = {3, 3, 1}
Output: 3.00
Approach: The given problem can be solved by using the Greedy Approach. The idea is to sort the array in ascending order and choose the groups of size X because the average is inversely proportional to the number of elements. Finally, add the remaining elements to the last group. Follow the below steps to solve the problem:
- Sort the given array arr[] in ascending order.
- Initialize the variables, say sum, res, and count as 0 to store the sum of array elements, result, and the count of elements in the current group.
- Iterate over the range [0, N] using the variable i and perform the following steps:
- Add the value of arr[i] to the variable sum and increase the value of count by 1.
- If the value of count is equal to X, and the remaining array elements can’t form a group then add them to the current group and add the average in the variable res.
- Otherwise, add the average of the group formed so far in the variable res.
- After completing the above steps, print the value of res as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum// of average of groupsvoid maxAverage(int A[], int N, int X, int Y){ // Sort the given array sort(A, A + N); int sum = 0; // Stores the sum of averages double res = 0; // Stores count of array element int count = 0; for (int i = 0; i < N; i++) { // Add the current value to // the variable sum sum += A[i]; // Increment the count by 1 count++; // If the current size is X if (count == X) { // If the remaining elements // can't become a group if (N - i - 1 < X) { i++; int cnt = 0; // Iterate until i is // less than N while (i < N) { cnt++; sum += A[i]; i++; } // Update the value of X X = X + cnt; // Update the average res += (double)sum / double(X); break; } // Find the average res += (double)sum / double(X); // Reset the sum and count sum = 0; count = 0; } } // Print maximum sum of averages cout << fixed << setprecision(2) << res << "\n";}// Driver Codeint main(){ int A[] = { 4, 10, 6, 5 }; int N = sizeof(A) / sizeof(A[0]); int X = 2, Y = 3; maxAverage(A, N, X, Y); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum sum// of average of groupsstatic void maxAverage(int A[], int N, int X, int Y){ // Sort the given array Arrays.sort(A); int sum = 0; // Stores the sum of averages double res = 0; // Stores count of array element int count = 0; for(int i = 0; i < N; i++) { // Add the current value to // the variable sum sum += A[i]; // Increment the count by 1 count++; // If the current size is X if (count == X) { // If the remaining elements // can't become a group if (N - i - 1 < X) { i++; int cnt = 0; // Iterate until i is // less than N while (i < N) { cnt++; sum += A[i]; i++; } // Update the value of X X = X + cnt; // Update the average res += (double)sum / (double)(X); break; } // Find the average res += (double)sum / (double)(X); // Reset the sum and count sum = 0; count = 0; } } // Print maximum sum of averages System.out.println(res);}// Driver Codepublic static void main(String[] args){ int A[] = { 4, 10, 6, 5 }; int N = A.length; int X = 2, Y = 3; maxAverage(A, N, X, Y);}}// This code is contributed by gauravrajput1 |
Python3
# Python 3 program for the above approach# Function to find the maximum sum# of average of groupsdef maxAverage(A,N,X,Y): # Sort the given array A.sort() sum = 0 # Stores the sum of averages res = 0 # Stores count of array element count = 0 for i in range(N): # Add the current value to # the variable sum sum += A[i] # Increment the count by 1 count += 1 # If the current size is X if (count == X): # If the remaining elements # can't become a group if (N - i - 1 < X): i += 1 cnt = 0 # Iterate until i is # less than N while (i < N): cnt += 1 sum += A[i] i += 1 # Update the value of X X = X + cnt # Update the average res += sum / X break # Find the average res += sum / X # Reset the sum and count sum = 0 count = 0 # Print maximum sum of averages print(res)# Driver Codeif __name__ == '__main__': A = [4, 10, 6, 5] N = len(A) X = 2 Y = 3 maxAverage(A, N, X, Y) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;public class GFG{// Function to find the maximum sum// of average of groupsstatic void maxAverage(int []A, int N, int X, int Y){ // Sort the given array Array.Sort(A); int sum = 0; // Stores the sum of averages double res = 0; // Stores count of array element int count = 0; for(int i = 0; i < N; i++) { // Add the current value to // the variable sum sum += A[i]; // Increment the count by 1 count++; // If the current size is X if (count == X) { // If the remaining elements // can't become a group if (N - i - 1 < X) { i++; int cnt = 0; // Iterate until i is // less than N while (i < N) { cnt++; sum += A[i]; i++; } // Update the value of X X = X + cnt; // Update the average res += (double)sum / (double)(X); break; } // Find the average res += (double)sum / (double)(X); // Reset the sum and count sum = 0; count = 0; } } // Print maximum sum of averages Console.WriteLine(res);}// Driver Codepublic static void Main(String[] args){ int []A = { 4, 10, 6, 5 }; int N = A.Length; int X = 2, Y = 3; maxAverage(A, N, X, Y);}} // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum sum // of average of groups function maxAverage(A, N, X, Y) { // Sort the given array A.sort(function (a, b) { return a - b; }) let sum = 0; // Stores the sum of averages let res = 0; // Stores count of array element let count = 0; for (let i = 0; i < N; i++) { // Add the current value to // the variable sum sum += A[i]; // Increment the count by 1 count++; // If the current size is X if (count == X) { // If the remaining elements // can't become a group if (N - i - 1 < X) { i++; let cnt = 0; // Iterate until i is // less than N while (i < N) { cnt++; sum += A[i]; i++; } // Update the value of X X = X + cnt; // Update the average res += sum / X; break; } // Find the average res += sum / X; // Reset the sum and count sum = 0; count = 0; } } // Print maximum sum of averages document.write(res.toPrecision(3)) } // Driver Code let A = [4, 10, 6, 5]; let N = A.length; let X = 2, Y = 3; maxAverage(A, N, X, Y); // This code is contributed by Potta Lokesh</script> |
Output:
12.50
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
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!
