Dada una array arr[] que consta de N enteros, la tarea es imprimir el menor de los dos subconjuntos obtenidos al dividir la array en dos subconjuntos de modo que la suma del subconjunto más pequeño se maximice.
Ejemplos:
Entrada: arr[] = {5, 3, 2, 4, 1, 2}
Salida: 4 5
Explicación:
Divida la array en dos subconjuntos como {4, 5} y {1, 2, 2, 3}.
El subconjunto {4, 5} es de longitud mínima, es decir 2, teniendo suma máxima = 4 + 5 = 9.Entrada: arr[] = {20, 15, 20, 50, 20}
Salida: 15 50
Enfoque: El problema dado se puede resolver usando Hashing y Sorting .
Siga los pasos a continuación para resolver el problema:
- Inicialice un HashMap , digamos M , para almacenar la frecuencia de cada carácter de la array arr[] .
- Recorra la array arr[] e incremente el recuento de cada carácter en HashMap M .
- Inicialice 2 variables, digamos S y flag , para almacenar la suma del primer subconjunto y para almacenar si existe una respuesta o no, respectivamente.
- Ordene la array arr[] en orden ascendente .
- Inicialice una ArrayList , digamos ans , para almacenar los elementos del subconjunto resultante.
- Recorra la array arr[] en orden inverso y realice los siguientes pasos:
- Almacene la frecuencia del carácter actual en una variable, digamos F .
- Si (F + ans.size()) es menor que ( N – (F + ans.size())), agregue el elemento arr[i] en ArrayList ans F varias veces.
- Disminuir el valor de i por F .
- Si el valor de S es mayor que la suma de los elementos de la array , marque la bandera como verdadera y luego rompa .
- Después de completar los pasos anteriores, si el valor de flag es true , imprima ArrayList ans como el subconjunto resultante. De lo contrario, imprima -1 .the
A continuación se muestra la implementación del enfoque anterior:
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 maximized
static 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 Code
int 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 approach
import 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 approach from collections import defaultdict # Function to split array elements # into two subsets having sum of # the smaller subset maximized def 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 Code if __name__ == "__main__": arr = [5, 3, 2, 4, 1, 2] findSubset(arr) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to split array elements
// into two subsets having sum of
// the smaller subset maximized
static 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 Code
public 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 maximized
function 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 Code
var arr = [5, 3, 2, 4, 1, 2 ];
findSubset(arr);
// This code is contributed by rutvik_56.
</script>
Producción:
4 5
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)