Sum of all possible strings obtained by removal of non | C ++ program for the above approach ; Function to convert a character to its equivalent digit ; Function to precompute powers of 10 ; Function to precompute prefix sum of numerical strings ; Function to return the i - th term of Triangular Number ; Function to return the sum of all resulting strings ; Precompute powers of 10 ; Precompute prefix sum ; Initialize result ; Apply the above general formula for every i ; Return the answer ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 10 ; int pref [ N ] , power [ N ] ; int toDigit ( char ch ) { return ( ch - '0' ) ; } void powerOf10 ( ) { power [ 0 ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) power [ i ] = power [ i - 1 ] * 10 ; } void precomputePrefix ( string str , int n ) { pref [ 0 ] = str [ 0 ] - '0' ; for ( int i = 1 ; i < n ; i ++ ) pref [ i ] = pref [ i - 1 ] + toDigit ( str [ i ] ) ; } int triangularNumber ( int i ) { int res = i * ( i + 1 ) / 2 ; return res ; } int sumOfSubstrings ( string str ) { int n = str . size ( ) ; powerOf10 ( ) ; precomputePrefix ( str , n ) ; int ans = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { ans += ( pref [ n - i - 2 ] * ( i + 1 ) + toDigit ( str [ n - i - 1 ] ) * triangularNumber ( n - i - 1 ) ) * power [ i ] ; } return ans ; } int main ( ) { string str = "1234" ; cout << sumOfSubstrings ( str ) ; return 0 ; }