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 indicesvoid 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 Codeint 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 indicesdef 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 Codeif __name__ == '__main__': # Given string S = "9999999999" # Length of the string N = len(S) # Function call findSumOfExpressions(S, N) |
C#
// C# program to implement// the above approachusing 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 indicesfunction 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 stringlet S = "9999999999" // Length of the stringlet N = S.length// Function callfindSumOfExpressions(S, N)// This code is contributed by phasing17. |
Output:
12656242944
Time Complexity: O(2N * 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!
