Suma de todas las subsecuencias de una array

Dada una array de n enteros. Encuentra la suma de todas las subsecuencias posibles de una array. 

Ejemplos: 

Input : arr[] = { 1, 2 }
Output : 6
All possible subsequences are {}, {1}, {2} 
and { 1, 2 }

Input : arr[] = { 1, 2, 3 }
Output : 24

Ya hemos discutido dos soluciones diferentes en la publicación a continuación. 
Suma de todos los subarreglos | Serie 1

En este post se discute una solución diferente. Echemos un vistazo más de cerca al problema e intentemos encontrar un patrón.  

Let a[] = { 1, 2, 3 }

All subsequences are {}, {1}, {2}, {3}, {1, 2}, 
                     {1, 3}, {2, 3}, {1, 2, 3}

So sum of subsequences are 0 + 1 + 2 + 3 + 3 + 
                             4 + 5 + 6 = 24

Here we can observe that in sum every elements 
occurs 4 times. Or in general every element 
will occur 2^(n-1) times. And we can also 
observe that sum of array elements is 6. So
final result will be 6*4.

En general, podemos encontrar la suma de todas las subsecuencias sumando todos los elementos de la array multiplicados por 2 ^(n-1), donde n es el número de elementos de la array.

Implementación:

// CPP program to find sum of
// all subarrays of array
#include <bits/stdc++.h>
using namespace std;
 
// To find sum of all subsequences
int findSum(int arr[], int n)
{
    // Sum all array elements
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // Result is sum * 2^(n-1)
    return sum * (1 << (n - 1));
}
 
// Driver program to test findSum()
int main()
{
    int arr[] = { 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSum(arr, n);
    return 0;
}

// Java program to find sum of
// all subarrays of array
 
public class Main {
    // To find sum of all subsequences
    static int findSum(int arr[], int n)
    {
        // Sum all array elements
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
 
        // Result is sum * 2^(n-1)
        return sum * (1 << (n - 1));
    }
 
    // Driver program to test findSum()
    public static void main(String[] args)
    {
        int arr[] = { 1, 2 };
        int n = arr.length;
        System.out.print(findSum(arr, n));
    }
}

# Python program to find sum of
# all subarrays of array
 
# To find sum of all subsequences
def findSum(arr, n):
     
    # Sum all array elements
    sum = 0
    for i in range(n):
        sum += arr[i]
  
    # Result is sum * 2^(n-1)
    return sum * (1 << (n - 1))
  
# Driver program to test findSum()
arr = [1, 2]
n = len(arr)
print findSum(arr, n)
 
# This code is submitted by Sachin Bisht

// C# program to find sum of
// all subarrays of array
using System;
 
class GFG
{
 
// To find sum of all subsequences
static int findSum(int []arr, int n)
{
    // Sum all array elements
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // Result is sum * 2^(n-1)
    return sum * (1 << (n - 1));
}
 
// Driver Code
static public void Main ()
{
    int []arr = { 1, 2 };
    int n = arr.Length;
    Console.WriteLine(findSum(arr, n));
}
}
 
// This code is contributed by ajit

<?php
// PHP program to find sum of
// all subarrays of array
 
// To find sum of all subsequences
 
function findSum($arr, $n)
{
    // Sum all array elements
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += $arr[$i];
 
    // Result is sum * 2^(n-1)
    return $sum * (1 << ($n - 1));
}
 
// Driver Code
$arr = array( 1, 2 );
$n = sizeof($arr);
 
echo findSum($arr, $n);
 
// This code is contributed by ajit
?>

<script>
 
// Javascript program to find sum of
// all subarrays of array
 
// To find sum of all subsequences
function findSum(arr, n)
{
     
    // Sum all array elements
    let sum = 0;
    for(let i = 0; i < n; i++)
        sum += arr[i];
 
    // Result is sum * 2^(n-1)
    return sum * (1 << (n - 1));
}
 
// Driver code
let arr = [ 1, 2 ];
let n = arr.length;
 
document.write(findSum(arr, n));
 
// This code is contributed by rameshtravel07
 
</script>

6

Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.