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 increasingly. 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.
- For each element traverse from the starting of the duplicate and:
- Return the result array.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to find out the largest subset // for each array element vector<int> max_subset(int a[], int n) { // Making another copy of array vector<int> v, ans; for (int i = 0; i < n; i++) v.push_back(a[i]); // Sorting the vector sort(v.begin(), v.end()); // Iterating over every elements // of the array for (int i = 0; i < n; i++) { // Finding the maximum number // of elements whose sum // is less than a[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; } // Driver code int main() { int arr[] = { 5, 2, 1, 1, 1, 6, 8 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call vector<int> ans = max_subset(arr, N); for (int x : ans) cout << x << " "; return 0; }
Java
// Java implementation of above approach import java.io.*; import java.util.*; class GFG { // Function to find out the largest subset // for each array element static ArrayList<Integer> max_subset(int[] a, int n) { // Making another copy of array ArrayList<Integer> v = new ArrayList<Integer>(); ArrayList<Integer> ans = new ArrayList<Integer>(); for (int i = 0; i < n; i++) v.add(a[i]); // Sorting the vector Collections.sort(v); // Iterating over every elements // of the array for (int i = 0; i < n; i++) { // Finding the maximum number // of elements whose sum // is less than a[i] int sum = 0, maxi = 0; for (int j = 0; j < n; j++) { sum += (int)v.get(j); if (sum >= a[i]) { maxi = j; break; } } ans.add(maxi); } return ans; } // Driver Code public static void main(String[] args) { int[] arr = { 5, 2, 1, 1, 1, 6, 8 }; int N = arr.length; // Function call ArrayList<Integer> ans = max_subset(arr, N); for(int x : ans) System.out.print(x + " "); } } // This code is contributed by sanjoy_62.
Python3
# Python3 code to implement the above approach # function to find the largest subset for each # array element def max_subset(a, n): # making a copy if a v = a.copy() ans = [] # sorting v v.sort() # iterating over a for i in range(n): # finding the max number of elements # whose sum is less than a[i] sums = 0 maxi = 0 for j in range(n): sums += v[j] if sums >= a[i]: maxi = j break ans.append(maxi) return ans # Driver Code arr = [5, 2, 1, 1, 1, 6, 8] N = len(arr) # Function call ans = max_subset(arr, N) print(" ".join(list(map(str, ans)))) # This code is contributed by phasing7.
C#
// C# code to implement above approach using System; using System.Collections; class GFG { // Function to find out the largest subset // for each array element static ArrayList max_subset(int[] a, int n) { // Making another copy of array ArrayList v = new ArrayList(); ArrayList ans = new ArrayList(); for (int i = 0; i < n; i++) v.Add(a[i]); // Sorting the vector v.Sort(); // Iterating over every elements // of the array for (int i = 0; i < n; i++) { // Finding the maximum number // of elements whose sum // is less than a[i] int sum = 0, maxi = 0; for (int j = 0; j < n; j++) { sum += (int)v[j]; if (sum >= a[i]) { maxi = j; break; } } ans.Add(maxi); } return ans; } // Driver code public static void Main() { int[] arr = { 5, 2, 1, 1, 1, 6, 8 }; int N = arr.Length; // Function call ArrayList ans = max_subset(arr, N); foreach(int x in ans) Console.Write(x + " "); } } // This code is contributed by Samim Hossain Mondal.
Javascript
<script> // JavaScript code for the above approach // Function to find out the largest subset // for each array element function max_subset(a, n) { // Making another copy of array let v = [], ans = []; for (let i = 0; i < n; i++) v.push(a[i]); // Sorting the vector v.sort(); // Iterating over every elements // of the array for (let i = 0; i < n; i++) { // Finding the maximum number // of elements whose sum // is less than a[i] let sum = 0, maxi = 0; for (let j = 0; j < n; j++) { sum += v[j]; if (sum >= a[i]) { maxi = j; break; } } ans.push(maxi); } return ans; } // Driver code let arr = [5, 2, 1, 1, 1, 6, 8]; let N = arr.length; // Function call let ans = max_subset(arr, N); for (let x of ans) document.write(x + " ") // This code is contributed by Potta Lokesh </script>
3 1 0 0 0 4 4
Time complexity: O(N2)
Auxiliary Space: O(1)
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++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to find the largest subset // with sum less than arr[i] vector<int> max_subset(int a[], int n) { // Making another copy of array vector<int> v, ans; for (int i = 0; i < n; i++) v.push_back(a[i]); // Sorting the vector sort(v.begin(), v.end()); // Prefix sum array int pref[n]; pref[0] = v[0]; for (int i = 1; i < n; i++) pref[i] = pref[i - 1] + v[i]; // Iterating over every elements // of the array for (int i = 0; i < n; i++) { // Using prefix array and // lower_bound() function for // finding the maximum number // of elements auto it = lower_bound(pref, pref + n, a[i]); int maxi = it - pref; ans.push_back(maxi); } return ans; } // Driver code int main() { int arr[] = { 5, 2, 1, 1, 1, 6, 8 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call vector<int> ans = max_subset(arr, N); for (int x : ans) cout << x << " "; return 0; }
Java
import java.util.*; import java.io.*; // Java program for the above approach class GFG{ static int lower_bound(int arr[], int x){ int n = arr.length; int l = 0, r = n, ans = n, mid; while(l <= r){ mid = (l + r)/2; if(arr[mid] >= x){ ans = mid; r = mid - 1; }else{ l = mid + 1; } } return ans; } // Function to find the largest subset // with sum less than arr[i] static ArrayList<Integer> max_subset(int a[], int n) { // Making another copy of array ArrayList<Integer> v = new ArrayList<Integer>(); ArrayList<Integer> ans = new ArrayList<Integer>(); for (int i = 0 ; i < n ; i++){ v.add(a[i]); } // Sorting the vector Collections.sort(v); // Prefix sum array int pref[] = new int[n]; pref[0] = v.get(0); for (int i = 1 ; i < n ; i++){ pref[i] = pref[i - 1] + v.get(i); } // Iterating over every elements // of the array for (int i = 0 ; i < n ; i++) { // Using prefix array and // lower_bound() function for // finding the maximum number // of elements int it = lower_bound(pref, a[i]); int maxi = it; ans.add(maxi); } return ans; } public static void main(String args[]) { int arr[] = new int[]{ 5, 2, 1, 1, 1, 6, 8 }; int N = arr.length; // Function call ArrayList<Integer> ans = max_subset(arr, N); for(int i = 0 ; i < ans.size() ; i++){ System.out.print(ans.get(i) + " "); } } } // This code is contributed by subhamgoyal2014.
Python3
# Python3 code to implement the above approach from bisect import bisect_left # Function to find the largest subset # with sum less than arr[i] def max_subset(a, n): # making another copy of the array v = a.copy() ans = [] # sorting v v.sort() # prefix sum array pref = [v[0]] for i in range(n - 1): pref.append(pref[i] + v[i + 1]) # iterating over ever element # of the array for i in range(n): # using prefix array and bisect_left() Function # for finding the max number of elements # bisect_left(pref, a[i]) returns the rightmost element # greater than or equal to a[i] it = bisect_left(pref, a[i]) maxi = it ans.append(maxi) return ans # Driver Code arr = [5, 2, 1, 1, 1, 6, 8] N = len(arr) print(" ".join(map(str, max_subset(arr, N)))) # This code is contributed by phasing17.
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ static int lower_bound(int []arr, int x){ int n = arr.Length; int l = 0, r = n, ans = n, mid; while(l <= r){ mid = (l + r)/2; if(arr[mid] >= x){ ans = mid; r = mid - 1; }else{ l = mid + 1; } } return ans; } // Function to find the largest subset // with sum less than arr[i] static List<int> max_subset(int []a, int n) { // Making another copy of array List<int> v = new List<int>(); List<int> ans = new List<int>(); for (int i = 0 ; i < n ; i++){ v.Add(a[i]); } // Sorting the vector v.Sort(); // Prefix sum array int []pref = new int[n]; pref[0] = v[0]; for (int i = 1 ; i < n ; i++){ pref[i] = pref[i - 1] + v[i]; } // Iterating over every elements // of the array for (int i = 0 ; i < n ; i++) { // Using prefix array and // lower_bound() function for // finding the maximum number // of elements int it = lower_bound(pref, a[i]); int maxi = it; ans.Add(maxi); } return ans; } public static void Main(String []args) { int []arr = new int[]{ 5, 2, 1, 1, 1, 6, 8 }; int N = arr.Length; // Function call List<int> ans = max_subset(arr, N); for(int i = 0 ; i < ans.Count ; i++){ Console.Write(ans[i] + " "); } } } // This code contributed by shikhasingrajput
Javascript
<script> // JavaScript code for the above approach // Function to find out the largest subset // for each array element function max_subset(a, n) { // Making another copy of array let v = [], ans = []; for (let i = 0; i < n; i++) v.push(a[i]); // Sorting the vector v.sort(); // Iterating over every elements // of the array for (let i = 0; i < n; i++) { // Finding the maximum number // of elements whose sum // is less than a[i] let sum = 0, maxi = 0; for (let j = 0; j < n; j++) { sum += v[j]; if (sum >= a[i]) { maxi = j; break; } } ans.push(maxi); } return ans; } // Driver code let arr = [5, 2, 1, 1, 1, 6, 8]; let N = arr.length; // Function call let ans = max_subset(arr, N); for (let x of ans) document.write(x + " ") // This code is contributed by code_hunt. </script>
3 1 0 0 0 4 4
Time complexity: O(N * log(N))
Auxiliary Space: O(N)
Contact Us