Smallest subset of maximum sum possible by splitting array into two subsets
Given an array arr[] consisting of N integers, the task is to print the smaller of the two subsets obtained by splitting the array into two subsets such that the sum of the smaller subset is maximized.
Examples:
Input: arr[] = {5, 3, 2, 4, 1, 2}
Output: 4 5
Explanation:
Split the array into two subsets as {4, 5} and {1, 2, 2, 3}.
The subset {4, 5} is of minimum length, i.e. 2, having maximum sum = 4 + 5 = 9.Input: arr[] = {20, 15, 20, 50, 20}
Output: 15 50
Approach: The given problem can be solved by using Hashing and Sorting.
Follow the steps below to solve the problem:
- Initialize a HashMap, say M, to store the frequency of each character of the array arr[].
- Traverse the array arr[] and increment the count of every character in the HashMap M.
- Initialize 2 variables, say S, and flag, to store the sum of the first subset and to store if an answer exists or not respectively.
- Sort the array arr[] in ascending order.
- Initialize an ArrayList, say ans, to store the elements of the resultant subset.
- Traverse the array arr[] in reverse order and perform the following steps:
- Store the frequency of the current character in a variable, say F.
- If (F + ans.size()) is less than (N – (F + ans.size())) then append the element arr[i] in the ArrayList ans F number of times.
- Decrement the value of i by F.
- If the value of S is greater than the sum of the array elements, then mark the flag as true and then break.
- After completing the above steps, if the value of flag is true, then print the ArrayList ans as the resultant subset. Otherwise, print -1.the
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to split array elements// into two subsets having sum of// the smaller subset maximizedstatic void findSubset(vector<int> arr){ // Stores the size of the array int N = arr.size(); // Stores the frequency // of array elements map<int,int> mp; // Stores the total // sum of the array int totSum = 0; // Stores the sum of // the resultant set int s = 0; // Stores if it is possible // to split the array that // satisfies the conditions int flag = 0; // Stores the elements // of the first subseta vector<int> ans; // Traverse the array arr[] for (int i = 0; i < arr.size(); i++) { // Increment total sum totSum += arr[i]; // Increment count of arr[i] mp[arr[i]]=mp[arr[i]]+1; } // Sort the array arr[] sort(arr.begin(),arr.end()); // Stores the index of the // last element of the array int i = N - 1; // Traverse the array arr[] while (i >= 0) { // Stores the frequency // of arr[i] int frq = mp[arr[i]]; // If frq + ans.size() is // at most remaining size if ((frq + ans.size()) < (N - (frq + ans.size()))) { for (int k = 0; k < frq; k++) { // Append arr[i] to ans ans.push_back(arr[i]); // Decrement totSum by arr[i] totSum -= arr[i]; // Increment s by arr[i] s += arr[i]; i--; } } // Otherwise, decrement i // by frq else { i -= frq; } // If s is greater // than totSum if (s > totSum) { // Mark flag 1 flag = 1; break; } } // If flag is equal to 1 if (flag == 1) { // Print the arrList ans for (i = ans.size() - 1; i >= 0; i--) { cout<<ans[i]<<" "; } } // Otherwise, print "-1" else { cout<<-1; }}// Driver Codeint main(){ vector<int> arr = { 5, 3, 2, 4, 1, 2 }; findSubset(arr);}// This code is contributed by mohit kumar 29. |
Java
// Java program for above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to split array elements // into two subsets having sum of // the smaller subset maximized static void findSubset(int[] arr) { // Stores the size of the array int N = arr.length; // Stores the frequency // of array elements Map<Integer, Integer> map = new HashMap<>(); // Stores the total // sum of the array int totSum = 0; // Stores the sum of // the resultant set int s = 0; // Stores if it is possible // to split the array that // satisfies the conditions int flag = 0; // Stores the elements // of the first subset ArrayList<Integer> ans = new ArrayList<>(); // Traverse the array arr[] for (int i = 0; i < arr.length; i++) { // Increment total sum totSum += arr[i]; // Increment count of arr[i] map.put(arr[i], map.getOrDefault( arr[i], 0) + 1); } // Sort the array arr[] Arrays.sort(arr); // Stores the index of the // last element of the array int i = N - 1; // Traverse the array arr[] while (i >= 0) { // Stores the frequency // of arr[i] int frq = map.get(arr[i]); // If frq + ans.size() is // at most remaining size if ((frq + ans.size()) < (N - (frq + ans.size()))) { for (int k = 0; k < frq; k++) { // Append arr[i] to ans ans.add(arr[i]); // Decrement totSum by arr[i] totSum -= arr[i]; // Increment s by arr[i] s += arr[i]; i--; } } // Otherwise, decrement i // by frq else { i -= frq; } // If s is greater // than totSum if (s > totSum) { // Mark flag 1 flag = 1; break; } } // If flag is equal to 1 if (flag == 1) { // Print the arrList ans for (i = ans.size() - 1; i >= 0; i--) { System.out.print( ans.get(i) + " "); } } // Otherwise, print "-1" else { System.out.print(-1); } } // Driver Code public static void main(String[] args) { int[] arr = { 5, 3, 2, 4, 1, 2 }; findSubset(arr); }} |
Python3
# Python 3 program for the above approachfrom collections import defaultdict# Function to split array elements# into two subsets having sum of# the smaller subset maximizeddef findSubset(arr): # Stores the size of the array N = len(arr) # Stores the frequency # of array elements mp = defaultdict(int) # Stores the total # sum of the array totSum = 0 # Stores the sum of # the resultant set s = 0 # Stores if it is possible # to split the array that # satisfies the conditions flag = 0 # Stores the elements # of the first subseta ans = [] # Traverse the array arr[] for i in range(len(arr)): # Increment total sum totSum += arr[i] # Increment count of arr[i] mp[arr[i]] = mp[arr[i]]+1 # Sort the array arr[] arr.sort() # Stores the index of the # last element of the array i = N - 1 # Traverse the array arr[] while (i >= 0): # Stores the frequency # of arr[i] frq = mp[arr[i]] # If frq + ans.size() is # at most remaining size if ((frq + len(ans)) < (N - (frq + len(ans)))): for k in range(frq): # Append arr[i] to ans ans.append(arr[i]) # Decrement totSum by arr[i] totSum -= arr[i] # Increment s by arr[i] s += arr[i] i -= 1 # Otherwise, decrement i # by frq else: i -= frq # If s is greater # than totSum if (s > totSum): # Mark flag 1 flag = 1 break # If flag is equal to 1 if (flag == 1): # Print the arrList ans for i in range(len(ans) - 1, -1, -1): print(ans[i], end = " ") # Otherwise, print "-1" else: print(-1)# Driver Codeif __name__ == "__main__": arr = [5, 3, 2, 4, 1, 2] findSubset(arr) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to split array elements// into two subsets having sum of// the smaller subset maximizedstatic void findSubset(List<int> arr){ // Stores the size of the array int N = arr.Count; int i; // Stores the frequency // of array elements Dictionary<int,int> mp = new Dictionary<int,int>(); // Stores the total // sum of the array int totSum = 0; // Stores the sum of // the resultant set int s = 0; // Stores if it is possible // to split the array that // satisfies the conditions int flag = 0; // Stores the elements // of the first subseta List<int> ans = new List<int>(); // Traverse the array arr[] for (i = 0; i < arr.Count; i++) { // Increment total sum totSum += arr[i]; // Increment count of arr[i] if(mp.ContainsKey(arr[i])) mp[arr[i]]=mp[arr[i]]+1; else mp.Add(arr[i],1); } // Sort the array arr[] arr.Sort(); // Stores the index of the // last element of the array i = N - 1; // Traverse the array arr[] while (i >= 0) { // Stores the frequency // of arr[i] int frq = mp[arr[i]]; // If frq + ans.size() is // at most remaining size if ((frq + ans.Count) < (N - (frq + ans.Count))) { for (int k = 0; k < frq; k++) { // Append arr[i] to ans ans.Add(arr[i]); // Decrement totSum by arr[i] totSum -= arr[i]; // Increment s by arr[i] s += arr[i]; i--; } } // Otherwise, decrement i // by frq else { i -= frq; } // If s is greater // than totSum if (s > totSum) { // Mark flag 1 flag = 1; break; } } // If flag is equal to 1 if (flag == 1) { // Print the arrList ans for (i = ans.Count - 1; i >= 0; i--) { Console.Write(ans[i]+" "); } } // Otherwise, print "-1" else { Console.Write(-1); }}// Driver Codepublic static void Main(){ List<int> arr = new List<int>(){ 5, 3, 2, 4, 1, 2 }; findSubset(arr);}}// This code is contributed by ipg2016107. |
Javascript
<script>// Javascript program for the above approach// Function to split array elements// into two subsets having sum of// the smaller subset maximizedfunction findSubset(arr){ // Stores the size of the array var N = arr.length; // Stores the frequency // of array elements var mp = new Map(); // Stores the total // sum of the array var totSum = 0; // Stores the sum of // the resultant set var s = 0; // Stores if it is possible // to split the array that // satisfies the conditions var flag = 0; // Stores the elements // of the first subseta var ans = []; // Traverse the array arr[] for (var i = 0; i < arr.length; i++) { // Increment total sum totSum += arr[i]; // Increment count of arr[i] if(mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i])+1) else mp.set(arr[i], 1); } // Sort the array arr[] arr.sort((a,b)=> a-b) // Stores the index of the // last element of the array var i = N - 1; // Traverse the array arr[] while (i >= 0) { // Stores the frequency // of arr[i] var frq = mp.get(arr[i]); // If frq + ans.size() is // at most remaining size if ((frq + ans.length) < (N - (frq + ans.length))) { for (var k = 0; k < frq; k++) { // Append arr[i] to ans ans.push(arr[i]); // Decrement totSum by arr[i] totSum -= arr[i]; // Increment s by arr[i] s += arr[i]; i--; } } // Otherwise, decrement i // by frq else { i -= frq; } // If s is greater // than totSum if (s > totSum) { // Mark flag 1 flag = 1; break; } } // If flag is equal to 1 if (flag == 1) { // Print the arrList ans for (i = ans.length - 1; i >= 0; i--) { document.write( ans[i] + " "); } } // Otherwise, print "-1" else { document.write(-1); }}// Driver Codevar arr = [5, 3, 2, 4, 1, 2 ];findSubset(arr);// This code is contributed by rutvik_56.</script> |
Output:
4 5
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
