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 groups void 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 Code int 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 approach import java.util.*; Â
class GFG{ Â
// Function to find the maximum sum // of average of groups static 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 Code public 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 groups def 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 Code if __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 approach using System; Â
public class GFG{ Â
// Function to find the maximum sum // of average of groups static 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 Code public 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> |
12.50
Â
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!