Sum of all possible strings obtained by removal of non | Python 3 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
N = 10 NEW_LINE pref = [ 0 ] * N NEW_LINE power = [ 0 ] * N NEW_LINE def toDigit ( ch ) : NEW_LINE INDENT return ( ord ( ch ) - ord ( '0' ) ) NEW_LINE DEDENT def powerOf10 ( ) : NEW_LINE INDENT power [ 0 ] = 1 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT power [ i ] = power [ i - 1 ] * 10 NEW_LINE DEDENT DEDENT def precomputePrefix ( st , n ) : NEW_LINE INDENT pref [ 0 ] = ( ord ( st [ 0 ] ) - ord ( '0' ) ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT pref [ i ] = ( pref [ i - 1 ] + toDigit ( st [ i ] ) ) NEW_LINE DEDENT DEDENT def triangularNumber ( i ) : NEW_LINE INDENT res = i * ( i + 1 ) // 2 NEW_LINE return res NEW_LINE DEDENT def sumOfSubstrings ( st ) : NEW_LINE INDENT n = len ( st ) NEW_LINE powerOf10 ( ) NEW_LINE precomputePrefix ( st , n ) NEW_LINE ans = 0 NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT ans += ( ( pref [ n - i - 2 ] * ( i + 1 ) + toDigit ( st [ n - i - 1 ] ) * triangularNumber ( n - i - 1 ) ) * power [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT st = "1234" NEW_LINE print ( sumOfSubstrings ( st ) ) NEW_LINE DEDENT