Given an array, arr[] and integer K, the task is to find the maximum number of non-overlapping subsets such that the sum of the subsets is strictly greater than K when you may also change the value of each element to the maximum value of the particular subset.

Examples:

Input: arr[]= {90, 80, 70, 60, 50, 100}, K = 180
Output: 2

Input: arr[] = {3, 2, 1}, K = 8
Output: 1

Approach: To solve the problem follow the below idea:

In order to form a maximum number of subsets we need to form a sequence with a minimum number of elements as well as the sum of values of elements should be greater than K. We start forming subsequences with elements having maximum value and changing the rest of the element value to the maximum value in the same subsequence.

Follow the steps mentioned below to implement the idea:  

• Sort the array arr[] in non-increasing order
• Take a pointer i initially at 0.
• Iterate over the array and form subset with arr[i] with minimum possible elements.
• Check if the elements already used + the elements required (d/arr[i] +1) for forming the current subset is less than or equal to the total number of elements then increase the subset formed and move pointer i to the next index.
• Else, a return number of subsequences is formed as there are not enough elements available to form more subsets.

Below is the implementation of the above approach:

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;

// Function for finding out maximum
// subsequences formed
int maximumSequence(vector<int>& arr, int K, int n)
{

    // Sorting array in non-increasing order
    sort(arr.begin(), arr.end(), greater<int>());

    int i = 0;
    int sequence_formed = 0;
    int elements_required = 0;

    while (elements_required + (K / arr[i]) + 1 <= n) {

        // Increasing Sequence formed
        sequence_formed += 1;

        // After forming of a new sequence,
        // increasing elements used who have
        // assigned to any of the subsequence
        elements_required += ((K / arr[i]) + 1);

        i++;
    }

    return sequence_formed;
}

// Driver code
int main()
{
    vector<int> power = { 90, 80, 70, 60, 50, 100 };
    int n = power.size();

    int k = 180;

    // Function call
    cout << maximumSequence(power, k, n);
}

2

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

Related Articles:

• Introduction to Arrays – Data Structure and Algorithm Tutorials