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;
}