Sum of all possible expressions of a numeric string possible by inserting addition operators

Last Updated : 27 Dec, 2022

Given a numeric string str of length N, the task is to find the sum of all possible expressions by inserting the '+' operator between the characters of the string any number of times.

Examples:

Input: str = "125" Output: 176 Explanation: Inserting "+" after 1st index modifies str to "1+25" and value = 26 Inserting "+" after 2nd index modifies str to "12+5" and value = 17 Inserting "+" after both 1st and 2nd index modifies str to "1+2+5" and value = 8 Therefore, the total sum of all possible expression is 125 + 26 + 17 + 8 = 176

Input: str = "9999999999"
Output: 12656242944

Approach: The idea is to insert the '+' operator at all possible index of the string in all possible ways and calculate the sum. Finally, print the total sum obtained. Follow the steps below to solve the problem:

Initialize a variable say, sumOfExp to store the sum of all possible expression by inserting the '+' operator at all possible indices of the string.
Generate all possible subset of indices of the string iteratively. For every subset of indices inserts the '+' operator at elements of the subset and increment sumOfExp by the sum of the current expression.
Finally, print the value of sumOfExp.

Below is the implementation of the above approach:

C++

// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find sum of all expressions by // inserting '+' operator at all possible indices void findSumOfExpressions(string S, int N) {  // Stores sum of all expressions by inserting  // '+' operator at all possible indices  unsigned long long sumOfExp = 0;  // Generate all possible subset  // of indices iteratively  for (int i = 0; i < pow(2, N - 1); i++) {  // Stores sum of  // current expressions  unsigned long long ans_sub = 0;  // Stores numbers of  // current expressions  string subst = string(1, S.at(0));  // Traverse the string at insert + at  // current subset of indices  for (int j = 0; j < N - 1; j++) {  // If current index exists  // in the current subset  if (((i >> j) & 1) == 1) {  // Update ans_sub  ans_sub += stoull(subst);  // Update subset  subst = string(1, S.at(j + 1));  }  else  // Update subset  subst += S.at(j + 1);  // + can't be inserted after  // the last index  if (j == N - 2)  ans_sub += stoull(subst);  }  // Update ans  sumOfExp += ans_sub;  }  // Base case  if (N == 1)  cout << S;  else  // Print answer  cout << sumOfExp; } // Driver Code int main() {  // Given string  string S = "9999999999";  // Length of the string  int N = S.length();  // Function call  findSumOfExpressions(S, N); } // This code is contributed by phasing17.

Java

import java.util.List; import java.util.ArrayList; class Main {    // Function to find sum of all expressions by  // inserting '+' operator at all possible indices  static void findSumOfExpressions(String S, int N)   {    // Stores sum of all expressions by inserting  // '+' operator at all possible indices  long sumOfExp = 0;  // Generate all possible subset  // of indices iteratively  for (int i = 0; i < Math.pow(2, N - 1); i++) {  // Stores sum of  // current expressions  long ans_sub = 0;  // Stores numbers of  // current expressions  String subst = "" + S.charAt(0);  // Traverse the string at insert + at  // current subset of indices  for (int j = 0; j < N - 1; j++) {  // If current index exists  // in the current subset  if (((i >> j) & 1) == 1) {  // Update ans_sub  ans_sub += Long.parseLong(subst);  // Update subset  subst = "" + S.charAt(j + 1);   }  else  // Update subset  subst += S.charAt(j + 1);  // + can't be inserted after  // the last index  if (j == N - 2)  ans_sub += Long.parseLong(subst);  }  // Update ans  sumOfExp += ans_sub;  }  // Base case  if (N == 1)  System.out.println(S);  else  // Print answer  System.out.println(sumOfExp);  }  // Driver Code  public static void main(String[] args)   {    // Given string  String S = "9999999999";  // Length of the string  int N = S.length();  // Function call  findSumOfExpressions(S, N);  } } // This code is contributed by phasing17.

Python3

# Python program to implement # the above approach # Function to find sum of all expressions by # inserting '+' operator at all possible indices def findSumOfExpressions(S, N): # Stores sum of all expressions by inserting # '+' operator at all possible indices sumOfExp = 0 # Generate all possible subset # of indices iteratively for i in range(2 ** (N - 1)): # Stores sum of  # current expressions ans_sub = 0 # Stores numbers of # current expressions subst = S[0] # Traverse the string at insert + at # current subset of indices for j in range(N - 1): # If current index exists # in the current subset if (i >> j) & 1: # Update ans_sub ans_sub += int(subst) # Update subset subst = S[j + 1] else: # Update subset subst += S[j + 1] # + can't be inserted after # the last index  if j == N - 2: ans_sub += int(subst) # Update ans sumOfExp += ans_sub # Base case  if N == 1: print(int(S)) else: # Print answer print(sumOfExp) # Driver Code if __name__ == '__main__': # Given string S = "9999999999" # Length of the string N = len(S) # Function call findSumOfExpressions(S, N)

// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG {  // Function to find sum of all expressions by  // inserting '+' operator at all possible indices  static void findSumOfExpressions(string S, int N)  {    // Stores sum of all expressions by inserting  // '+' operator at all possible indices  ulong sumOfExp = 0;    // Generate all possible subset  // of indices iteratively  for (int i = 0; i < Math.Pow(2, N - 1); i++) {  // Stores sum of  // current expressions  ulong ans_sub = 0;    // Stores numbers of  // current expressions  string subst = "" + S[0];    // Traverse the string at insert + at  // current subset of indices  for (int j = 0; j < N - 1; j++) {  // If current index exists  // in the current subset  if (((i >> j) & 1) == 1) {  // Update ans_sub  ans_sub += Convert.ToUInt64(subst);    // Update subset  subst = "" + S[j + 1];   }  else  // Update subset  subst += S[j + 1];    // + can't be inserted after  // the last index  if (j == N - 2)  ans_sub += Convert.ToUInt64(subst);  }    // Update ans  sumOfExp += ans_sub;  }  // Base case  if (N == 1)  Console.WriteLine(S);  else    // Print answer  Console.WriteLine(sumOfExp);  }  // Driver Code    public static void Main(string[] args)  {  // Given string  string S = "9999999999";    // Length of the string  int N = S.Length;    // Function call  findSumOfExpressions(S, N);  } } // This code is contributed by phasing17.

JavaScript

// JavaScript program to implement // the above approach // Function to find sum of all expressions by // inserting '+' operator at all possible indices function findSumOfExpressions(S, N) {  // Stores sum of all expressions by inserting  // '+' operator at all possible indices  let sumOfExp = 0  // Generate all possible subset  // of indices iteratively  for (var i = 0; i < 2 ** (N - 1); i++)  {  // Stores sum of   // current expressions  let ans_sub = 0  // Stores numbers of  // current expressions  let subst = S[0]  // Traverse the string at insert + at  // current subset of indices  for (var j = 0; j < N - 1; j++)  {  // If current index exists  // in the current subset  if (((i >> j) & 1) == 1)  {  // Update ans_sub  ans_sub += parseInt(subst)  // Update subset  subst = S[j + 1]  }  else  // Update subset  subst += S[j + 1]  // + can't be inserted after  // the last index   if (j == N - 2)  ans_sub += parseInt(subst)  }  // Update ans  sumOfExp += ans_sub  }  // Base case   if (N == 1)  console.log(parseInt(S))  else  // Print answer  console.log(sumOfExp) } // Driver Code // Given string let S = "9999999999"   // Length of the string let N = S.length // Function call findSumOfExpressions(S, N) // This code is contributed by phasing17.