Sum of all subsequences of an array
Given an array of n integers. Find the sum of all possible subsequences of an array.
Examples :
Input : arr[] = { 1, 2 } Output : 6 All possible subsequences are {}, {1}, {2} and { 1, 2 } Input : arr[] = { 1, 2, 3 } Output : 24
We have already discussed two different solutions in below post.
Sum of all Subarrays | Set 1
In this post a different solution is discussed. Let us take a closer look at the problem and try to find a pattern
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.
In general we can find sum of all subsequences by adding all elements of array multiplied by 2(n-1) where n is number of elements in array.
Implementation:
C++
// 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
// 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
# 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#
// 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 // 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 ?> |
Javascript
<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> |
Output
6