Dada una array arr[] de N enteros, la tarea es encontrar el recuento máximo de K , es decir, enteros consecutivos de 0 a K, que está presente en el conjunto S , donde S contiene todos los valores posibles de suma de subconjuntos de los array array [] .
Ejemplos:
Entrada: arr[] = {1, 3}
Salida: 2
Explicación: Los posibles subconjuntos son {}, {1}, {3}, {1, 3} y sus respectivas sumas son {0, 1, 3, 4} . Por lo tanto, la cuenta máxima de números enteros consecutivos a partir de 0 en el conjunto que contiene todas las sumas de los subconjuntos es 2 (es decir, {0, 1}).Entrada: arr[] = {1, 1, 1, 4}
Salida: 8
Explicación: El conjunto que contiene todas las sumas de subconjuntos de la array dada es {0, 1, 2, 3, 4, 5, 6, 7}. Por lo tanto, el recuento máximo de enteros consecutivos a partir de 0 es 8.
Enfoque ingenuo: el problema dado se puede resolver utilizando la programación dinámica manteniendo todas las sumas de subconjuntos posibles en una array que se realiza utilizando la técnica de la mochila . A partir de entonces, calcular el recuento máximo de enteros consecutivos.
Complejidad de tiempo: O(N*K) donde K representa la suma de todos los elementos en la array arr[] .
Espacio Auxiliar: O(K)
Enfoque eficiente: el problema anterior se puede resolver utilizando un enfoque codicioso . Supongamos que el conjunto que contiene todas las sumas de subconjuntos de la array arr[] contiene todos los enteros en el rango [0, X] . Si se introduce un nuevo número Y en la array, todos los enteros en el rango [Y, X + Y] también serán posibles como la suma del subconjunto. Usando esta observación, el problema dado se puede resolver siguiendo los pasos a continuación:
- Ordena la array dada en orden no decreciente.
- Mantenga una variable, digamos X como 0 , lo que denota que los enteros en el rango [0, X] son posibles como la suma del subconjunto de la array dada arr[] .
- Para mantener la continuidad de enteros consecutivos, arr[i] <= X + 1 debe cumplirse. Por lo tanto, recorra la array dada para cada i en el rango [0, N) , si el valor de arr[i] <= X + 1 , luego actualice el valor de X = X + arr[i] . De lo contrario, sal del bucle .
- Después de completar los pasos anteriores, el conteo de enteros en el rango [0, X] es decir, (X + 1) .
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 find maximum count of
// consecutive integers from 0 in set
// S of all possible subset-sum
int maxConsecutiveCnt(vector<int> arr)
{
// Stores the maximum possible integer
int X = 0;
// Sort the given array in
// non-decreasing order
sort(arr.begin(), arr.end());
// Iterate the given array
for (int i = 0; i < arr.size(); i++) {
// If arr[i] <= X+1, then update
// X otherwise break the loop
if (arr[i] <= (X + 1)) {
X = X + arr[i];
}
else {
break;
}
}
// Return Answer
return X + 1;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 1, 1, 4 };
cout << maxConsecutiveCnt(arr);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG {
// Function to find maximum count of
// consecutive integers from 0 in set
// S of all possible subset-sum
public static int maxConsecutiveCnt(int[] arr)
{
// Stores the maximum possible integer
int X = 0;
// Sort the given array in
// non-decreasing order
Arrays.sort(arr);
// Iterate the given array
for (int i = 0; i < arr.length; i++) {
// If arr[i] <= X+1, then update
// X otherwise break the loop
if (arr[i] <= (X + 1)) {
X = X + arr[i];
} else {
break;
}
}
// Return Answer
return X + 1;
}
// Driver Code
public static void main(String args[]) {
int[] arr = { 1, 1, 1, 4 };
System.out.println(maxConsecutiveCnt(arr));
}
}
// This code is contributed by gfgking.
Python3
# python program for the above approach # Function to find maximum count of # consecutive integers from 0 in set # S of all possible subset-sum def maxConsecutiveCnt(arr): # Stores the maximum possible integer X = 0 # Sort the given array in # non-decreasing order arr.sort() # Iterate the given array for i in range(0, len(arr)): # If arr[i] <= X+1, then update # X otherwise break the loop if (arr[i] <= (X + 1)): X = X + arr[i] else: break # Return Answer return X + 1 # Driver Code if __name__ == "__main__": arr = [1, 1, 1, 4] print(maxConsecutiveCnt(arr)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find maximum count of
// consecutive integers from 0 in set
// S of all possible subset-sum
public static int maxConsecutiveCnt(int[] arr)
{
// Stores the maximum possible integer
int X = 0;
// Sort the given array in
// non-decreasing order
Array.Sort(arr);
// Iterate the given array
for (int i = 0; i < arr.Length; i++)
{
// If arr[i] <= X+1, then update
// X otherwise break the loop
if (arr[i] <= (X + 1))
{
X = X + arr[i];
}
else
{
break;
}
}
// Return Answer
return X + 1;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 1, 1, 4 };
Console.Write(maxConsecutiveCnt(arr));
}
}
// This code is contributed by gfgking.
Javascript
// JavaScript Program to implement
// the above approach
// Function to find maximum count of
// consecutive integers from 0 in set
// S of all possible subset-sum
function maxConsecutiveCnt(arr)
{
// Stores the maximum possible integer
let X = 0;
// Sort the given array in
// non-decreasing order
arr.sort(function (a, b) { return a - b })
// Iterate the given array
for (let i = 0; i < arr.length; i++) {
// If arr[i] <= X+1, then update
// X otherwise break the loop
if (arr[i] <= (X + 1)) {
X = X + arr[i];
}
else {
break;
}
}
// Return Answer
return X + 1;
}
// Driver Code
let arr = [1, 1, 1, 4];
document.write(maxConsecutiveCnt(arr));
// This code is contributed by Potta Lokesh
</script>
8
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA