Given a string determine whether it is a ‘sum-string’. A string is called a sum-string if it
#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;
}