Largest Subset with sum less than each Array element

Given an array arr[] containing N elements, the task is to find the size of the largest subset for each array element arr[i] such that the sum of the subset is less than that element.

Examples:

Input: arr[] = { 5, 2, 1, 1, 1, 6, 8}
Output: 3 1 0 0 0 4 4
Explanation:
For i = 0 -> subset = {1, 1, 1}, sum = 3. No other larger subset has sum less than 5.
For i = 1 -> subset = {1}. Sum = 1 which is less than arr[1] = 2
For i = 2 -> subset = {}. No element with value less than 1 present in array.
For i = 3 and i = 4 also subsets will have no element.
For i = 5 -> subset = {2, 1, 1, 1}, sum = 5 which is less than arr[5] = 6 and largest in size.
For i = 6 -> subset = {2, 1, 1, 1}, sum = 5 which is less than arr[6] = 8 and largest in size.

Input: arr[] = { 2, 1, 4, 5, 3, 2, 1 }
Output: 1 0 2 3 2 1 0

Naive Approach: The simplest way to solve the problem is to form all the subsets for each arr[i] and find the largest one with a sum less than that element among all the subsets.

Time complexity: O(N*2N)
Auxiliary Space: O(2N)

Better Approach: A better approach to solve the problem is by using the Greedy method based on the following idea.

Make a copy of the actual array and sort the duplicate. After that for each array element (arr[i]) traverse the duplicate array and find the maximum of how many elements from the start can be added to a subset such that the sum is less than arr[i].

Follow the steps mentioned below to solve the problem:

  • Make a copy (say v) of the array.
  • Sort the duplicate in increasing order.
  • Traverse the array from i = 0 to N-1:
    • For each element traverse from the starting of the duplicate and:
      • Check if adding the current element of the duplicate keeps the sum less than arr[i] or not.
      • If the sum exceeds arr[i]break the loop.
      • Otherwise, traverse the loop and increase the size of the subset.
    • Add the subset size to the result array.
  • Return the result array.

Below is the implementation of the above approach.

C++

 

#include <bits/stdc++.h>

using namespace std;

 

vector<int> max_subset(int a[], int n)

{

    

    vector<int> v, ans;

    for (int i = 0; i < n; i++)

        v.push_back(a[i]);

 

    

    sort(v.begin(), v.end());

 

    

    

    for (int i = 0; i < n; i++) {

 

        

        

        

        int sum = 0, maxi = 0;

        for (int j = 0; j < n; j++) {

            sum += v[j];

            if (sum >= a[i]) {

                maxi = j;

                break;

            }

        }

        ans.push_back(maxi);

    }

    return ans;

}

 

int main()

{

    int arr[] = { 5, 2, 1, 1, 1, 6, 8 };

    int N = sizeof(arr) / sizeof(arr[0]);

 

    

    vector<int> ans = max_subset(arr, N);

    for (int x : ans)

        cout << x << " ";

    return 0;

}

Time complexity: O(N2)
Auxiliary Space: O(N)

Efficient Approach: The efficient approach is similar to the previous approach but it uses the concept of prefix sum and lower bound as mentioned here;

After sorting the duplicate array build a prefix sum array of the duplicate array.
For each element instead of iterating the duplicate array use lower bound in the prefix sum array to find the number of elements that can be included in a subset.

Follow the steps mentioned below:

  • Build a duplicate array and sort the duplicate (say v).
  • Build prefix array for v.
  • Iterate from i = 0 to N-1 in arr[]:
    • Use lower bound in prefix array and find how many elements can be included in the subset.
    • Add the subset size in the result array.
  • Return the result array.

Below is the implementation of the above approach.

C++

 

#include <bits/stdc++.h>

using namespace std;

 

vector<int> max_subset(int a[], int n)

{

    

    vector<int> v, ans;

    for (int i = 0; i < n; i++)

        v.push_back(a[i]);

 

    

    sort(v.begin(), v.end());

 

    

    int pref[n];

    pref[0] = v[0];

    for (int i = 1; i < n; i++)

        pref[i] = pref[i - 1] + v[i];

 

    

    

    for (int i = 0; i < n; i++) {

 

        

        

        

        

        auto it

            = lower_bound(pref,

                          pref + n, a[i]);

 

        int maxi = it - pref;

        ans.push_back(maxi);

    }

    return ans;

}

 

int main()

{

    int arr[] = { 5, 2, 1, 1, 1, 6, 8 };

    int N = sizeof(arr) / sizeof(arr[0]);

 

    

    vector<int> ans = max_subset(arr, N);

    for (int x : ans)

        cout << x << " ";

    return 0;

}

Time complexity: O(N * log(N))
Auxiliary Space: O(N)

Leave a Comment