*Java* very straightforward solution with detailed explanation

• The idea is quite straightforward:

1. Choose the first number `A`, it can be the leftmost `1` up to `i` digits. `i<=(L-1)/2` because the third number should be at least as long as the first number

2. Choose the second number `B`, it can be the leftmost `1` up to `j` digits excluding the first number. the limit for `j` is a little bit tricky, because we don't know whether `A` or `B` is longer. The remaining string (with length `L-j`) after excluding `A` and `B` should have a length of at least max(length `A`, length `B`), where length `A` = `i` and length `B` = `j-i`, thus `L-j >= max(j-i, i)`

3. Calls the recursive checker function and returns true if passes the checker function, or continue to the next choice of `B` (`A`) until there is no more choice for `B` or `A`, in which case returns a false.

Here is the code in Java:

``````    public boolean isAdditiveNumber(String num) {
int L = num.length();

// choose the first number A
for(int i=1; i<=(L-1)/2; i++) {
// A cannot start with a 0 if its length is more than 1
if(num.charAt(0) == '0' && i>=2) break; //previous code: continue;

// choose the second number B
for(int j=i+1; L-j>=j-i && L-j>=i; j++) {
// B cannot start with a 0 if its length is more than 1
if(num.charAt(i) == '0' && j-i>=2) break; // previous: continue;

long num1 = Long.parseLong(num.substring(0, i)); // A
long num2 = Long.parseLong(num.substring(i, j)); // B
String substr = num.substring(j); // remaining string

if(isAdditive(substr, num1, num2)) return true; // return true if passes isAdditive test
// else continue; // continue for loop if does not pass isAdditive test
}
}
return false; // does not pass isAdditive test, thus is not additive
}

// Recursively checks if a string is additive
public boolean isAdditive(String str, long num1, long num2) {
if(str.equals("")) return true; // reaches the end of string means a yes

long sum = num1+num2;
String s = ((Long)sum).toString();
if(!str.startsWith(s)) return false; // if string does not start with sum of num1 and num2, returns false

return isAdditive(str.substring(s.length()), num2, sum); // recursively checks the remaining string
}
``````

If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java

• The "else continue;" part in the inner loop can be removed safely.

• Yes, you are right.

• What is the time complexity?

• It should be discussed whether "11" "1" is additive.

• @XiaoboZhang1991, there is no need to think about `11` or `1` because the problem states the following:

``````A valid additive sequence should contain at least three numbers.
``````

As of the time complexity, since we have two `for` loops, the time complexity should be O(n^2) where n is the length of the number.

• in this statement " if (num.charAt(0) == '0' && i >= 2) continue;", why is it "continue", but not "break"?

• I agree with you. We can simply break and save a little computation
Once num.charAt(0) == '0', the only possible first number is 0, no need to check 0x 0xx 0xxx
Same goes with the next continue

• @yanlantao, @stupidbird911, both of you are right. We can safely break if we notice it starts with a 0 and its length is larger than 1.

• Is there any thought of solving the follow up "How would you handle overflow for very large input integers?"

• I believe that this code can handle the large case input, right?

``````class Solution {
public:
if (num.length() < 3) return false;
int len = num.length();
// first chhose A, A <= (len - 1) / 2
for (int i = 1; i <= (len - 1) / 2; i++) {
if (num[0] == '0' && i >= 2) break; // break this loop when the first digit is zero
string A = num.substr(0, i);
// second choose B
for (int j = 1; ; j++) {
if (len - (i + j) < max(i, j)) break;
if (num[i] == '0' && j >= 2) break;
string B = num.substr(i, j);
if ( isAdditive( num.substr(i + j), A, B ) ) return true;
}
}
return false;
}

bool isAdditive(string str, string A, string B) {
if (str == "") return true;
if ( ! ( str.find( des ) == 0 ) ) return false;
}

string addDigit(string A, string B) {
int pA = A.length() - 1;
int pB = B.length() - 1;
string des = "";
int carry = 0;
while (pA >= 0 && pB >= 0) {
int tmp = (A[pA] - '0') + (B[pB] - '0') + carry;
des = (char)('0' + tmp % 10) + des;
carry = tmp / 10;
pA--;
pB--;
}
while (pA >= 0) {
int tmp = (A[pA] - '0') + carry;
des = (char)('0' + tmp % 10) + des;
carry = tmp / 10;
pA--;
}
while (pB >= 0) {
int tmp = (B[pB] - '0') + carry;
des = (char)('0' + tmp % 10) + des;
carry = tmp / 10;
pB--;
}
if (carry)
des = '1' + des;
return des;
}
};``````

• Great solution. Just translate it to Python:

``````class Solution(object):
"""
:type num: str
:rtype: bool
"""
# Idea: find the first 2 strings and then continue to check the remaining strings
L = len(num)
# 1st number is num[0:i], 2nd number is num[i:j]
for i in range(1, L/2+1):
if num[0] == '0' and i >= 2: break
for j in range(i+1, min(L-i, (L+i)/2)+1):
if num[i] == '0' and j-i >= 2: break     # means starting with "0", e.g., "03"
num1 = num[0:i]
num2 = num[i:j]
remain = num[j:]
return True

return False

if remain == "":    # means checked whole string
return True
total = str( int(num1) + int(num2) )
if remain.startswith(total):
else:
return False

``````

• why allow so much slack room for the leading 0? if you only check that you're using a number with a leading 0 when i >= 2, then you've already absorbed more than 1 digit, and that causes problems

it should be i>=1 no?

• great solution, easy to understand, thx

• shouldnt complexity of this solution be 0(N3) ?

• thanks for sharing, your solution is really smart.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.