Maximize sum of averages of subsequences of lengths lying in a given range

0 0 6 minutes read

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>

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 zambiatek!