Given a number as string s, find the sum of all the elements present in all possible subsequences of s.
Examples :
Input : s = "123"
Output : 24
Explanation : all possible sub-sequences are
1, 2, 3, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}
which add up to 24
Input : s = "453"
Output : 48
Brute Force Approach:
Calculate the sum of all possible subsequences of a given string ‘s’. It does so by generating all possible subsequences of the given string and then computing the sum of each subsequence.
Algorithm:
- Declare an integer variable ‘n’ to store the length of the input string ‘s’ using the size() function.
- Declare an integer variable ‘ans’ to store the sum of all possible subsequences.
- Generate all possible subsequences of the input string ‘s’ using a nested loop.
- The outer loop generates all possible binary numbers with ‘n’ bits (from 0 to 2^n – 1).
- The inner loop checks each bit of the binary number and includes the corresponding character of the input string ‘s’ in the subsequence if the bit is set to 1.
- Compute the sum of the generated subsequence and add it to the variable ‘ans’.
- Print the variable ‘ans’ as the output of the program.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int main(){ // Initialize the input string 's' string s = "453"; // Get the length of the input string 's' int n = s.size(); // Initialize the variable 'ans' to store the sum of all // subsequences int ans = 0; // Generate all possible subsequences for (int i = 0; i < (1 << n); i++) { // Loop through all binary numbers from 0 to // (2^n - 1) int sum = 0; // Initialize the sum of the current // subsequence to 0 for (int j = 0; j < n; j++) { // Check each bit of the current binary // number if (i & (1 << j)) { // If the jth bit of the current // binary number is set sum += (s[j] - '0'); // Add the corresponding // character of the input // string 's' to the current // subsequence } } ans += sum; // Add the sum of the current // subsequence to the total sum of all // subsequences } // Print the sum of all possible subsequences as the // output of the program cout << ans << endl; return 0;} |
Java
import java.util.*;class Main { public static void main(String[] args) { // Initialize the input string 's' String s = "453"; // Get the length of the input string 's' int n = s.length(); // Initialize the variable 'ans' to // store the sum of all subsequences int ans = 0; // Generate all possible subsequences for (int i = 0; i < (1 << n); i++) { // Loop through all binary numbers from 0 to (2^n - 1) int sum = 0; // Initialize the sum of the current subsequence to 0 for (int j = 0; j < n; j++) { // Check each bit of the current binary number if ((i & (1 << j)) != 0) { // If the jth bit of the current binary number is set sum += (s.charAt(j) - '0'); // Add the corresponding character of the input string 's' to the current subsequence } } ans += sum; // Add the sum of the current subsequence to the total sum of all subsequences } // Print the sum of all possible subsequences // as the output of the program System.out.println(ans); }} |
Python3
def generateSubsequences(s): # Get the length of the input string 's' n = len(s) # Initialize the variable 'ans' to store the sum of all subsequences ans = 0 # Generate all possible subsequences for i in range(1 << n): # Loop through all binary numbers from 0 to (2^n - 1) sum = 0 # Initialize the sum of the current subsequence to 0 for j in range(n): # Check each bit of the current binary number if i & (1 << j): # If the jth bit of the current binary number is set # Add the corresponding character of the input string 's' to the current subsequence sum += int(s[j]) ans += sum # Add the sum of the current subsequence to the total sum of all subsequences # Return the sum of all possible subsequences as the output of the function return ans# Driver programs = "453"print(generateSubsequences(s)) |
Javascript
// Initialize the input string 's'let s = "453";// Get the length of the input string 's'let n = s.length;// Initialize the variable 'ans' to store the sum of all// subsequenceslet ans = 0;// Generate all possible subsequencesfor (let i = 0; i < (1 << n); i++) { // Loop through all binary numbers from 0 to (2^n - 1) let sum = 0; // Initialize the sum of the current subsequence to 0 for (let j = 0; j < n; j++) { // Check each bit of the current binary number if (i & (1 << j)) { // If the jth bit of the current binary number is set sum += parseInt(s[j]); // Add the corresponding character of the input string 's' // to the current subsequence } } ans += sum; // Add the sum of the current subsequence to the total sum of all // subsequences}// Print the sum of all possible subsequences as the output of the programconsole.log(ans); |
C#
using System;class Program { static void Main(string[] args) { // Initialize the input string 's' string s = "453"; // Get the length of the input string 's' int n = s.Length; // Initialize the variable 'ans' to store the sum of // all subsequences int ans = 0; // Generate all possible subsequences for (int i = 0; i < (1 << n); i++) { // Loop through all binary numbers from // 0 to // (2^n - 1) int sum = 0; // Initialize the sum of the // current subsequence to 0 for (int j = 0; j < n; j++) { // Check each bit of the current // binary number if ((i & (1 << j)) != 0) { // If the jth bit of the current // binary number is set sum += (s[j] - '0'); // Add the corresponding // character of the // input string 's' to // the current // subsequence } } ans += sum; // Add the sum of the current // subsequence to the total sum of // all subsequences } // Print the sum of all possible subsequences as the // output of the program Console.WriteLine(ans); }} |
Output
48
Time Complexity: O(2^n * n)
Auxiliary Space: O(1)
Power Set Approach: Using power set, we can find all the subsequences and sum up all the subsequences individually in a different function. The total number of subsequences possible is 2n-1. Add the sum of all subsequences to the combined sum which is the final output.
Algorithm:
- Create a function named “findSubSequence” with an int return type that takes two parameters, a string “s” and an integer “num”. This function will return the numeric value of a subsequence of s.
- Create a variable named “res” and initialize it with 0 and another variable “i” of int type and initialize it with again 0.
- Run a while loop till “num” > 0
- check if the i-th bit is set (i.e., it is equal to 1). If yes, add the numeric value of the i-th character of s (obtained by subtracting the character ‘0’) to res.
- then increment i by 1 and right shift num by 1.
- return the value of res.
- Create a function with an int return type named “combinedSum” which takes string “s” as the input parameter.
- Create an int variable “n” and initialize it with the length of the string.
- Create another int variable “c_sum” and initialize it with 0.
- Calculate the number of subsequences of s as range = (1 << n) – 1
- start a for loop and iterate it through all the subsequences by iterating from 0 to range.
- In each iteration, call the function findSubSequence with the string s and the current subsequence number i. Add the returned value to c_sum
- return c_sum.
Below is the implementation of above approach.
C++
// CPP program to find the sum of// elements present in all subsequences#include <bits/stdc++.h>using namespace std;// Returns numeric value of a subsequence of// s. The subsequence to be picked is decided// using bit pattern of num (We pick all those// digits for which there is a set bit in num)int findSubSequence(string s, int num){ // Initialize the result int res = 0; // till n!=0 int i = 0; while (num) { // if i-th bit is set // then add this number if (num & 1) res += s[i] - '0'; i++; // right shift i num = num >> 1; } return res;}// function to find combined sum// of all individual subsequence sumint combinedSum(string s){ // length of string int n = s.length(); // stores the combined int c_sum = 0; // 2^n-1 subsequences int range = (1 << n) - 1; // loop for all subsequences for (int i = 0; i <= range; i++) c_sum += findSubSequence(s, i); // returns the combined sum return c_sum;}// driver codeint main(){ string s = "123"; cout << combinedSum(s); return 0;} |
Java
// Java program to find the sum of elements// present in all subsequencesimport java.io.*;class GFG { // Returns numeric value of a // subsequence of s. The subsequence // to be picked is decided using bit // pattern of num (We pick all those // digits for which there is a set // bit in num) static int findSubSequence(String s, int num) { // Initialize the result int res = 0; // till n!=0 int i = 0; while (num > 0) { // if i-th bit is set // then add this number if ((num & 1) == 1) res += s.charAt(i) - '0'; i++; // right shift i num = num >> 1; } return res; } // function to find combined sum // of all individual subsequence // sum static int combinedSum(String s) { // length of String int n = s.length(); // stores the combined int c_sum = 0; // 2^n-1 subsequences int range = (1 << n) - 1; // loop for all subsequences for (int i = 0; i <= range; i++) c_sum += findSubSequence(s, i); // returns the combined sum return c_sum; } // Driver function public static void main (String[] args) { String s = "123"; System.out.println(combinedSum(s)); }}// This code is contributed by Anuj_ 67 |
Python 3
# Python 3 program to find the sum of# elements present in all subsequences # Returns numeric value of a subsequence of# s. The subsequence to be picked is decided# using bit pattern of num (We pick all those# digits for which there is a set bit in num)def findSubSequence(s, num): # Initialize the result res = 0 # till n!=0 i = 0 while (num) : # if i-th bit is set # then add this number if (num & 1): res += ord(s[i]) - ord('0') i+=1 # right shift i num = num >> 1 return res # function to find combined sum# of all individual subsequence sumdef combinedSum(s): # length of string n = len(s) # stores the combined c_sum = 0 # 2^n-1 subsequences ran = (1 << n) - 1 # loop for all subsequences for i in range( ran+1): c_sum += findSubSequence(s, i) # returns the combined sum return c_sum # driver codeif __name__ == "__main__": s = "123" print(combinedSum(s)) |
C#
// C# program to find the sum of elements// present in all subsequencesusing System;class GFG { // Returns numeric value of a // subsequence of s. The subsequence // to be picked is decided using bit // pattern of num (We pick all those // digits for which there is a set // bit in num) static int findSubSequence(string s, int num) { // Initialize the result int res = 0; // till n!=0 int i = 0; while (num > 0) { // if i-th bit is set // then add this number if ((num & 1) == 1) res += s[i] - '0'; i++; // right shift i num = num >> 1; } return res; } // function to find combined sum // of all individual subsequence // sum static int combinedSum(string s) { // length of string int n = s.Length; // stores the combined int c_sum = 0; // 2^n-1 subsequences int range = (1 << n) - 1; // loop for all subsequences for (int i = 0; i <= range; i++) c_sum += findSubSequence(s, i); // returns the combined sum return c_sum; } // Driver function public static void Main() { string s = "123"; Console.Write(combinedSum(s)); }}// This code is contributed by Sam007 |
PHP
<?php// PHP program to find the sum of// elements present in all subsequences// Returns numeric value of a subsequence of// s. The subsequence to be picked is decided// using bit pattern of num (We pick all those// digits for which there is a set bit in num)function findSubSequence($s, $num){ // Initialize the result $res = 0; // till n!=0 $i = 0; while ($num) { // if i-th bit is set // then add this number if ($num & 1) $res += $s[$i] - '0'; $i++; // right shintift i $num = $num >> 1; } return $res;}// function to find combined sum// of all individual subsequence sumfunction combinedSum(string $s){ // length of string $n = strlen($s); // stores the combined $c_sum = 0; // 2^n-1 subsequences $range = (1 << $n) - 1; // loop for all subsequences for ($i = 0; $i <= $range; $i++) $c_sum += findSubSequence($s, $i); // returns the combined sum return $c_sum;} // Driver Code $s = "123"; echo combinedSum($s); // This code is contributed by Anuj_67?> |
Javascript
<script>// Javascript program to find the sum of elements// present in all subsequences // Returns numeric value of a // subsequence of s. The subsequence // to be picked is decided using bit // pattern of num (We pick all those // digits for which there is a set // bit in num) function findSubSequence(s,num) { // Initialize the result let res = 0; // till n!=0 let i = 0; while (num > 0) { // if i-th bit is set // then add this number if ((num & 1) == 1) res += s[i].charCodeAt(0) - '0'.charCodeAt(0); i++; // right shift i num = num >> 1; } return res; } // function to find combined sum // of all individual subsequence // sum function combinedSum(s) { // length of String let n = s.length; // stores the combined let c_sum = 0; // 2^n-1 subsequences let range = (1 << n) - 1; // loop for all subsequences for (let i = 0; i <= range; i++) c_sum += findSubSequence(s, i); // returns the combined sum return c_sum; } // Driver function let s = "123"; document.write(combinedSum(s)); // This code is contributed by avanitrachhadiya2155</script> |
Output
24
Time complexity :O(2^n * n)
Auxiliary Space:O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
