Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Example 1:
Input: "112358"
Output: true
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
Example 2:
Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Constraints:
num consists only of digits '0'-'9'. 1 <= num.length <= 35
/*
Method2: processing string for large number
The process for determining if the input is additive is the same as the previous method.
But, we made string additions and we compare strings only
Similar to the previous method, the process start be indentifying the starting 3 numbers: first, second, third
s.t., first+second = third
*/
//T(n) = O(n^3)
//S(n) = O(1)
class Solution {
public:
bool isAdditiveNumber(string num) {
/*
1. num can not be less than 3 in size
2. Note: num could have leading zero: i.e., "000", where '0' + '0' == '0'
*/
int len = num.size();
if (len < 3) { return false; }
//find the possible three starting numbers
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
for (int k = j + 1; k < len; k++) {
string first = num.substr(0, i - 0 + 1);
if (first.size() > 1 && first[0] == '0') { continue; }
string second = num.substr(i + 1, j - (i + 1) + 1);
if (second.size() > 1 && second[0] == '0') { continue; }
string third = num.substr(j + 1, k - (j + 1) + 1);
if (third.size() > 1 && third[0] == '0') { continue; }
string sum = add(first, second);
if (sum == third) {
//find our candidate
if (find(num, k + 1, second, third)) {
return true;
}
}
}
}
}
return false;
}
private:
//O(n), where n is num.size()
bool find(string& num, int pos, string first, string second) {
int len = num.size();
if (pos >= len) { return true; }
for (int i = pos; i < len; i++) {
string third = num.substr(pos, i - pos + 1);
string sum = add(first, second);
if (third == sum) {
if (find(num, i + 1, second, third)) {
return true;
}
}
}
return false;
}
//O(1), assuming the length of a or b does not exceed 20
string add(string& a, string& b) {
int lenA = a.size();
int lenB = b.size();
int left = lenA - 1;
int right = lenB - 1;
int carry = 0;
string res = "";
while (left >= 0 || right >= 0 || carry > 0) {
int op1 = 0;
int op2 = 0;
if (left >= 0) {
op1 = a[left--] - '0';
}
if (right >= 0) {
op2 = b[right--] - '0';
}
int sum = carry + op1 + op2;
res.push_back(sum % 10 + '0');
carry = sum / 10;
}
reverse(res.begin(), res.end());
return res;
}
};
/*
can not handle very large number, passing 40/41 cases
can not pass the case: "11111111111011111111111"
*/
#define ll long long
class Solution {
public:
bool isAdditiveNumber(string num) {
int len = num.size();
if (len < 3) {
return false;
}
return find(num);
}
bool find(string& num) {
int len = num.size();
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
string firstS = num.substr(0, i - 0 + 1);
string secondS = num.substr(i + 1, j - (i + 1) + 1);
if (firstS.size() > 1 && firstS[0] == '0') {
return false;
}
if (secondS.size() > 1 && secondS[0] == '0') {
continue;
}
ll first = stoll(firstS);
ll second = stoll(secondS);
if (check(num, j + 1, first, second)) {
return true;
}
}
}
return false;
}
bool check(string& num, int pos, int first, int second) {
int len = num.size();
for (int i = pos; i < len; i++) {
string thirdS = num.substr(pos, i - pos + 1);
if (thirdS.size() > 1 && thirdS[0] == '0') { return false; }
ll third = stoll(num.substr(pos, i - pos + 1));
if (first + second == third - second == first) {
if (i == len - 1) {
return true;
}
else if (check(num, i + 1, second, third)) {
return true;
}
}
}
return false;
}
};