Dada una array arr[] de longitud N , la tarea es encontrar la suma total de los subconjuntos de todos los subconjuntos de la array.
Ejemplos:
Entrada: arr[] = {1, 1}
Salida: 6
Todos los subconjuntos posibles:
a) {} : 0
Todos los subconjuntos posibles de este subconjunto
serán {}, Sum = 0
b) {1} : 1
Todos los subconjuntos posibles de este subconjunto
serán {} y {1}, Sum = 0 + 1 = 1
c) {1} : 1
Todos los posibles subconjuntos de este subconjunto
serán {} y {1}, Sum = 0 + 1 = 1
d ) {1, 1} : 4
Todos los subconjuntos posibles de este subconjunto
serán {}, {1}, {1} y {1, 1}, Suma = 0 + 1 + 1 + 2 = 4
Así, ans = 0 + 1 + 1 + 4 = 6
Entrada: arr[] = {1, 4, 2, 12}
Salida: 513
Enfoque: En este artículo, se discutirá un enfoque con complejidad de tiempo O(N) para resolver el problema dado.
La clave está en observar el número de veces que un elemento se repetirá en todos los subconjuntos.
Ampliemos la vista. Se sabe que cada elemento aparecerá 2 (N – 1) veces en la suma de subconjuntos. Ahora, ampliemos aún más la vista y veamos cómo varía el conteo con el tamaño del subconjunto.
Hay N – 1 C K – 1 subconjuntos de tamaño K para cada índice que lo incluye.
La contribución de un elemento para un subconjunto de tamaño K será igual a 2 (K – 1)veces su valor. Así, la contribución total de un elemento para todos los subconjuntos de longitud K será igual a N – 1 C K – 1 * 2 (K – 1)
La contribución total entre todos los subconjuntos será igual a:
N – 1 C N – 1 * 2 (N – 1) + N – 1 C N – 2 * 2 (N – 2 + N – 1 C N – 3 * 2 (N – 3) + … + N – 1 C 0 * 2 0 .
Ahora, se conoce la contribución de cada elemento en la respuesta final. Entonces, multiplícalo por la suma de todos los elementos de la array que darán la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define maxN 10
// To store factorial values
int fact[maxN];
// Function to return ncr
int ncr(int n, int r)
{
return (fact[n] / fact[r]) / fact[n - r];
}
// Function to return the required sum
int findSum(int* arr, int n)
{
// Initialising factorial
fact[0] = 1;
for (int i = 1; i < n; i++)
fact[i] = i * fact[i - 1];
// Multiplier
int mul = 0;
// Finding the value of multipler
// according to the formula
for (int i = 0; i <= n - 1; i++)
mul += (int)pow(2, i) * ncr(n - 1, i);
// To store the final answer
int ans = 0;
// Calculate the final answer
for (int i = 0; i < n; i++)
ans += mul * arr[i];
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 1 };
int n = sizeof(arr) / sizeof(int);
cout << findSum(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int maxN = 10;
// To store factorial values
static int []fact = new int[maxN];
// Function to return ncr
static int ncr(int n, int r)
{
return (fact[n] / fact[r]) / fact[n - r];
}
// Function to return the required sum
static int findSum(int[] arr, int n)
{
// Initialising factorial
fact[0] = 1;
for (int i = 1; i < n; i++)
fact[i] = i * fact[i - 1];
// Multiplier
int mul = 0;
// Finding the value of multipler
// according to the formula
for (int i = 0; i <= n - 1; i++)
mul += (int)Math.pow(2, i) * ncr(n - 1, i);
// To store the final answer
int ans = 0;
// Calculate the final answer
for (int i = 0; i < n; i++)
ans += mul * arr[i];
return ans;
}
// Driver code
public static void main(String []args)
{
int arr[] = { 1, 1 };
int n = arr.length;
System.out.println(findSum(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach maxN = 10 # To store factorial values fact = [0]*maxN; # Function to return ncr def ncr(n, r) : return (fact[n] // fact[r]) // fact[n - r]; # Function to return the required sum def findSum(arr, n) : # Initialising factorial fact[0] = 1; for i in range(1, n) : fact[i] = i * fact[i - 1]; # Multiplier mul = 0; # Finding the value of multipler # according to the formula for i in range(n) : mul += (2 ** i) * ncr(n - 1, i); # To store the final answer ans = 0; # Calculate the final answer for i in range(n) : ans += mul * arr[i]; return ans; # Driver code if __name__ == "__main__" : arr = [ 1, 1 ]; n = len(arr); print(findSum(arr, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int maxN = 10;
// To store factorial values
static int []fact = new int[maxN];
// Function to return ncr
static int ncr(int n, int r)
{
return (fact[n] / fact[r]) / fact[n - r];
}
// Function to return the required sum
static int findSum(int[] arr, int n)
{
// Initialising factorial
fact[0] = 1;
for (int i = 1; i < n; i++)
fact[i] = i * fact[i - 1];
// Multiplier
int mul = 0;
// Finding the value of multipler
// according to the formula
for (int i = 0; i <= n - 1; i++)
mul += (int)Math.Pow(2, i) * ncr(n - 1, i);
// To store the final answer
int ans = 0;
// Calculate the final answer
for (int i = 0; i < n; i++)
ans += mul * arr[i];
return ans;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 1, 1 };
int n = arr.Length;
Console.WriteLine(findSum(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// To store factorial values
let fact = new Array(10);
// Function to return ncr
function ncr(n, r)
{
return (fact[n] / fact[r]) / fact[n - r];
}
// Function to return the required sum
function findSum(arr, n)
{
// Initialising factorial
fact[0] = 1;
for (let i = 1; i < n; i++)
fact[i] = i * fact[i - 1];
// Multiplier
let mul = 0;
// Finding the value of multipler
// according to the formula
for (let i = 0; i <= n - 1; i++)
mul += Math.pow(2, i) * ncr(n - 1, i);
// To store the final answer
let ans = 0;
// Calculate the final answer
for (let i = 0; i < n; i++)
ans += mul * arr[i];
return ans;
}
// Driver code
let arr = [ 1, 1 ];
let n = arr.length;
document.write(findSum(arr, n));
// This code is contributed by Mayank Tyagi
</script>
6
Complejidad de tiempo: O (Nlogn), donde N es el número de elementos en una array.
Complejidad espacial: O (N), para almacenar el factorial de números de 1 a N
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA