Sum of all substrings of a number

Sum of all substrings of a number: This is a standard interview problem asked in many interview coding rounds, also got featured in amazon coding rounds.
Submitted by Radib Kar, on June 12, 2020

Problem statement:

Given an integer, S represented as a string, get the sum of all possible substrings of this string.

Input:

A string S that representing the number.

Output:

Print sum of all possible substrings as required result.

Constraints:

1 <= T <= 100
1 <= S <= 1012

Example:

Input:

1234
326

Output:
1670
395

Explanation:

For the first input 1234, 
All possible substrings are
1, 2, 3, 4, 12, 13, 23, 34, 123, 234, 1234
Total sum = 1 + 2 + 3 + 4 + 12 + 23 + 34 + 123 + 234 + 1234 = 1670
For the second input 326
All possible substrings are
3, 2, 6
32, 26
326
Total sum=3+2+6+32+26+326= 395

Solution Approach:

The solution approach is by storing the substring sums to compute the exact next substring sum

  1. Create dp[n][n] to store substring sums;
  2. Initialize sum=0 which will be our final result;
  3. Base case computation (single length substrings),
    for i=0 to n-1,n= string length
        dp[i][i]=s[i] -'0'; //s[i]-'0' gives the digit actually
        sum+=dp[i][i];
    end for
    
  4. Till now we have computed all single digit substrings,
    for substring length,len=2 to n
        for start=0 to n-len
            //so basically it's the substring s[start,end]
            int end=start+len-1; 
            dp[start][end]=dp[start][end-1]*10+s[end]-'0';  
            sum+=dp[start][end];
        end for
    end for
    
  5. Sum is the final result.

All the statements are self-explanatory except the one which is the fundamental idea of the entire storing process. That is the below one,

dp[start][end]=dp[start][end-1]*10+s[end]-'0';

Let's check this with an example,

Say we are computing for string s="1234"
At some stage of computing,
Start=1, end= 3
So
Dp[start][end]=dp[start][end-1]*10+s[end]-'0'

So basically we are computing value of substring s[start..end] 
with help of already computed s[start,end-1]

For this particular example
s[start..end] ="234"
s[start..end-1] ="23"

Now, dp[1][3]=dp[1][2]*10+'4'-'0'

So, assuming the fact that our algo is correct and thus dp[start][end-1] 
has the correct value, dp[]1[2] would be 23 then
So,
dp[1][3]=23*10+'4'-'0=234
and that's true
So, here's the main logic
Now how dp[1][2] is guaranteed to be correct can be 
explored if we start filling the Dp table from the base conditions?

Let's start for the same example

N=4 here

So, we need to fill up a 4X4 DP table,

Sum of all substrings of a number (1)

After filling the base case,

Sum of all substrings of a number (2)

Now, I am computing for len=2

Start=0, end=1

Sum of all substrings of a number (3)

Start=1, end=2

Sum of all substrings of a number (4)

Start=2, end=3

Sum of all substrings of a number (5)

For len =3

Start=0, end=2

Sum of all substrings of a number (6)

Start=1, end=3

Sum of all substrings of a number (7)

Len=4

Start=0, end=3

Sum of all substrings of a number (8)

At each step we have summed up, so result is stored at sum.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

void print(vector<int> a, int n)
{
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

long long int my(string s, int n)
{

    long long int dp[n][n];
    long long int sum = 0;
    for (int i = 0; i < n; i++) {
        dp[i][i] = s[i] - '0';
        sum += dp[i][i];
    }

    for (int len = 2; len <= n; len++) {
        for (int start = 0; start <= n - len; start++) {
            int end = start + len - 1;
            dp[start][end] = dp[start][end - 1] * 10 + s[end] - '0';
            sum += dp[start][end];
        }
    }

    return sum;
}
int main()
{
    int t, n, item;

    cout << "enter the string: ";
    string s;
    cin >> s;
    
    cout << "sum of all possible substring is: " << my(s, s.length()) << endl;

    return 0;
}

Output:

RUN 1:
enter the string: 17678
sum of all possible substring is: 29011

RUN 2:
enter the string: 326
sum of all possible substring is: 395





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.