Home » Interview coding problems/challenges

Find out the sum-string

Find out the sum-string: Here, we are going to learn to check that the given string is a sum string or not using backtracking. Submitted by Souvik Saha, on February 03, 2020

Description

This is a standard interview problem to check that the given string is a sum string or not using backtracking.

Problem statement

There is a string given to you. You have to find out whether the given string is a sum string or not. For a string "12345168213" if it goes like this, "123" + "45" = "168" "45" + "168" = "213" then it is a sum string otherwise not.

    Input:
    Test case T
    T no. of strings we have to check. 

    E.g.
    3
    "12345168213"
    "123581321"
    "15643"
    
    Output:
    If the string is a sum-string then you have to print 
    "It is a sum string"
    and, if it is not then you have to print 
    "It is not a sum string".

Example

    T=3

    Str= "12345168213"

    "123" + "45" = "168"
    "45" + "168" = "213"
    It is a sum string

    Str= "123581321" 
    "1" + "2" = "3"
    "2" + "3" = "5"
    "3" + "5" = "8"
    "5" + "8" = "13"
    "8" + "13" = "21"
    It is a sum string

    Str= "15643"
    "1" + "5" = "6"
    "5" + "6" = "11"
    It is not a sum string

Explanation with example

To find out the actual length of the first two substrings is a problem of combination. We will solve the problem using the backtracking process. If we break the problem into sub-problems like,

1. Find out the length of the first sub-string.
2. Find out the length of the second sub-string.
3. Add the two strings.
4. Check if the summation is the same as the next substring.
5. If yes, we will continue the process otherwise the string is not a sum string.

    str.substring(i,j) + str.substring(j+1,k) = str.substring(k+1,l)
    str.substring(j+1,k) + str.substring(k+1,l) = str.substring(l+1,m)

Where, i, j, k, l, m is the position index on the substring of the string.

For the string "12345168213"

To find out the length of the first substring we will look for the all possible combination of the sub-string of the string from the starting index.

"1" , "12" , "123" , "1234" , "12345" , "123451" etc.

To find out the length of the second substring we will look for all possible combinations of the sub-string of the string from the last index of the first substring.

Let the first index= "123" then the all possible combinations are "4", "45", "451", "4516" etc.

After calculating the summation of the two sub-strings will also find out the length of the result and take the next sub-string who has a length equal to that length.

If the two substrings are "123" and "45" after calculating the summation the result "168" we will calculate its length which is equal to 3 and take the next sub-string e.g. "168"

Both the resultant and the sub-string are the same therefore we will add up "45" and "168" and check with "213".

C++ Implementation

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

//adding the numbers
string add(string str1, string str2)
{
    int len1 = str1.length();
    int len2 = str2.length();
    int i = 1;
    int carry = 0;
    string str = "";

    while ((len1 - i) >= 0 && (len2 - i) >= 0) {
        int result = (str1[len1 - i] - '0') + (str2[len2 - i] - '0') + carry;
        char ch = (result % 10) + '0';
        str = ch + str;
        carry = result / 10;
        i++;
    }

    while ((len1 - i) >= 0) {
        int result = (str1[len1 - i] - '0') + carry;
        char ch = (result % 10) + '0';
        str = ch + str;
        carry = result / 10;
        i++;
    }

    while ((len2 - i) >= 0) {
        int result = (str2[len2 - i] - '0') + carry;
        char ch = (result % 10) + '0';
        str = ch + str;
        carry = result / 10;
        i++;
    }

    if (carry > 0) {
        char ch = carry + '0';
        str = ch + str;
    }

    return str;
}

bool checksumUtill(string str, int pos, int str1_len, int str2_len)
{
    int n = str.length();
    int i = str1_len, j = str2_len;

    //if the total sum of the current position and
    //both the strings is greater than total length
    if (pos + str1_len + str2_len >= n)
        return false;

    //calculate the sum
    string s = add(str.substr(pos, i), str.substr(pos + i, j));

    //if the next substring of pos+i+j is equals to the sum
    if (s == str.substr(pos + i + j, s.length())) {
        if (pos + i + j + s.length() == n)
            return true;
        return checksumUtill(str, pos + i, j, s.length());
    }
    return false;
}

bool check_sum_string(string str)
{
    if (str.length() == 0)
        return false;

    int str1_len = 1;
    int str2_len = 1;
    int pos = 0;

    //go for all the combinations
    for (int i = 1; i < str.length(); i++) {
        for (int j = 1; j < str.length(); j++) {
            if (checksumUtill(str, pos, i, j)) {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int t;

    cout << "Test Case : ";
    cin >> t;

    while (t--) {
        string str;
        cout << "Enter the String : ";
        cin >> str;
        if (check_sum_string(str)) {
            cout << "It is a sum string\n";
        }
        else {
            cout << "It is not a sum string\n";
        }
    }
    return 0;
}

Output

Test Case : 3
Enter the String : 12345168213
It is a sum string
Enter the String : 123581321
It is a sum string
Enter the String : 15648
It is not a sum string