Sum of all substrings of a string representing a number - GeeksforGeeks
Given a integer represented as a string, we need to get the sum of all possible substrings of this string.
Read full article from Sum of all substrings of a string representing a number - GeeksforGeeks
Given a integer represented as a string, we need to get the sum of all possible substrings of this string.
We can solve this problem using dynamic programming. We can write summation of all substrings on basis of digit at which they are ending in that case,
Sum of all substrings = sumofdigit[0] + sumofdigit[1] + sumofdigit[2] … + sumofdigit[n-1] where n is length of string.
Sum of all substrings = sumofdigit[0] + sumofdigit[1] + sumofdigit[2] … + sumofdigit[n-1] where n is length of string.
Now we can get the relation between sumofdigit values and can solve the question iteratively. Each sumofdigit can be represented in terms of previous value as shown below,
For above example,
sumofdigit[3] = 4 + 34 + 234 + 1234
= 4 + 30 + 4 + 230 + 4 + 1230 + 4
= 4*4 + 10*(3 + 23 +123)
= 4*4 + 10*(sumofdigit[2])
In general,
sumofdigit[i] = (i+1)*num[i] + 10*sumofdigit[i-1]
Using above relation we can solve the problem in linear time. In below code a complete array is taken to store sumofdigit, as each sumofdigit value requires just previous value, we can solve this problem without allocating complete array also
int sumOfSubstrings(string num){ int n = num.length(); // allocate memory equal to length of string int sumofdigit[n]; // initialize first value with first digit sumofdigit[0] = toDigit(num[0]); int res = sumofdigit[0]; // loop over all digits of string for (int i=1; i<n; i++) { int numi = toDigit(num[i]); // update each sumofdigit from previous value sumofdigit[i] = (i+1) * numi + 10 * sumofdigit[i-1]; // add current value to the result res += sumofdigit[i]; } return res;}