306. Additive Number

  • 27.3%

https://leetcode.com/problems/additive-number/?tab=Description

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.

1
2
3
4
5
6
7
8
9
10
For example:
"112358" is an additive number because 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

"199100199" is also an additive number, the additive sequence is:
1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence
1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Follow up:

How would you handle overflow for very large input integers?


https://discuss.leetcode.com/topic/29872/0ms-concise-c-solution-perfectly-handles-the-follow-up-and-leading-0s

0ms concise C++ solution (perfectly handles the follow-up and leading 0s)

use a helper function to add two strings.

Choose first two number then recursively check.

Note that the length of first two numbers can’t be longer than half of the initial string, so the two loops in the first function will end when i>num.size()/2 and j>(num.size()-i)/2, this will actually save a lot of time.

Update the case of heading 0s

e.g. “100010” should return false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
bool isAdditiveNumber(string num) {
for(int i=1; i<=num.size()/2; i++){
for(int j=1; j<=(num.size()-i)/2; j++){
if(check(num.substr(0,i), num.substr(i,j), num.substr(i+j))) return true;
}
}
return false;
}
bool check(string num1, string num2, string num){
if(num1.size()>1 && num1[0]=='0' || num2.size()>1 && num2[0]=='0') return false;
string sum=add(num1, num2);
if(num==sum) return true;
if(num.size()<=sum.size() || sum.compare(num.substr(0,sum.size()))!=0) return false;
else return check(num2, sum, num.substr(sum.size()));
}
string add(string n, string m){
string res;
int i=n.size()-1, j=m.size()-1, carry=0;
while(i>=0 || j>=0){
int sum=carry+(i>=0 ? (n[i--]-'0') : 0) + (j>=0? (m[j--]-'0') : 0);
res.push_back(sum%10+'0');
carry=sum/10;
}
if(carry) res.push_back(carry+'0');
reverse(res.begin(), res.end());
return res;
}
};

https://discuss.leetcode.com/topic/29871/my-simple-c-non-recursion-solution

My Simple C++ Non-recursion Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
bool isAdditiveNumber(string num) {
for (int i = 1; i < num.size(); ++i) {
for (int j = i + 1; j < num.size(); ++j) {
string s1 = num.substr(0, i);
string s2 = num.substr(i, j - i);
long long d1 = atoll(s1.c_str()), d2 = atoll(s2.c_str());
if ((s1.size() > 1 && s1[0] == '0') || (s2.size() > 1 && s2[0] == '0')) continue;
long long next = d1 + d2;
string nexts = to_string(next);
string now = s1 + s2 + nexts;
while (now.size() < num.size()) {
d1 = d2;
d2 = next;
next = d1 + d2;
nexts = to_string(next);
now += nexts;
}
if (now == num) return true;
}
}
return false;
}
};

https://discuss.leetcode.com/topic/29856/java-recursive-and-iterative-solutions

Java Recursive and Iterative Solutions

The idea is quite straight forward. Generate the first and second of the sequence, check if the rest of the string match the sum recursively. i and j are length of the first and second number. i should in the range of [0, n/2]. The length of their sum should >= max(i,j)

Java Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.math.BigInteger;

public class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i <= n / 2; ++i) {
if (num.charAt(0) == '0' && i > 1) return false;
BigInteger x1 = new BigInteger(num.substring(0, i));
for (int j = 1; Math.max(j, i) <= n - i - j; ++j) {
if (num.charAt(i) == '0' && j > 1) break;
BigInteger x2 = new BigInteger(num.substring(i, i + j));
if (isValid(x1, x2, j + i, num)) return true;
}
}
return false;
}
private boolean isValid(BigInteger x1, BigInteger x2, int start, String num) {
if (start == num.length()) return true;
x2 = x2.add(x1);
x1 = x2.subtract(x1);
String sum = x2.toString();
return num.startsWith(sum, start) && isValid(x1, x2, start + sum.length(), num);
}
}
// Runtime: 8ms

Since isValid is a tail recursion it is very easy to turn it into a loop.

Java Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i <= n / 2; ++i)
for (int j = 1; Math.max(j, i) <= n - i - j; ++j)
if (isValid(i, j, num)) return true;
return false;
}
private boolean isValid(int i, int j, String num) {
if (num.charAt(0) == '0' && i > 1) return false;
if (num.charAt(i) == '0' && j > 1) return false;
String sum;
BigInteger x1 = new BigInteger(num.substring(0, i));
BigInteger x2 = new BigInteger(num.substring(i, i + j));
for (int start = i + j; start != num.length(); start += sum.length()) {
x2 = x2.add(x1);
x1 = x2.subtract(x1);
sum = x2.toString();
if (!num.startsWith(sum, start)) return false;
}
return true;
}
}
// Runtime: 9ms

If no overflow, instead of BigInteger we can consider to use Long which is a lot faster.

Java Iterative Using Long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i <= n / 2; ++i)
for (int j = 1; Math.max(j, i) <= n - i - j; ++j)
if (isValid(i, j, num)) return true;
return false;
}
private boolean isValid(int i, int j, String num) {
if (num.charAt(0) == '0' && i > 1) return false;
if (num.charAt(i) == '0' && j > 1) return false;
String sum;
Long x1 = Long.parseLong(num.substring(0, i));
Long x2 = Long.parseLong(num.substring(i, i + j));
for (int start = i + j; start != num.length(); start += sum.length()) {
x2 = x2 + x1;
x1 = x2 - x1;
sum = x2.toString();
if (!num.startsWith(sum, start)) return false;
}
return true;
}
}
// Runtime: 3ms

https://discuss.leetcode.com/topic/30453/java-very-straightforward-solution-with-detailed-explanation

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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


https://discuss.leetcode.com/topic/29868/backtracking-with-pruning-java-3-ms-solution-and-python-48-ms-solution

Backtracking with Pruning: Java 3 ms Solution and Python 48 ms Solution

Backtracking with Pruning.

Java (3 ms):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public boolean isAdditiveNumber(String num) {
if (num == null || num.length() < 3) return false;
int n = num.length();
for (int i = 1; i < n; i++) {
if (i > 1 && num.charAt(0) == '0') break;
for (int j = i+1; j < n; j++) {
int first = 0, second = i, third = j;
if (num.charAt(second) == '0' && third > second+1) break;
while (third < n) {
Long result = (Long.parseLong(num.substring(first, second)) +
Long.parseLong(num.substring(second, third)) );
if (num.substring(third).startsWith(result.toString())) {
first = second; second = third; third += result.toString().length();
}
else {
break;
}
}
if (third == n) return true;
}
}
return false;
}
}

Python (48 ms):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
def isAdditiveNumber(self, num):
"""
:type num: str
:rtype: bool
"""
if num is None or len(num) < 3:
return False
n = len(num)
for i in range(1, n):
if i > 1 and num[0] == '0':
break
for j in range(i+1, n):
first, second, third = 0, i, j
if num[second] == '0' and third > second + 1:
break
while third < n:
result = str(int(num[first:second]) + int(num[second:third]))
if num[third:].startswith(result):
first, second, third = second, third, third + len(result)
else:
break
if third == n:
return True
return False

python

72ms, 8.93%, October 18, 2016

https://discuss.leetcode.com/topic/29845/python-solution

Just trying all possibilities for the first two numbers and checking whether the rest fits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def isAdditiveNumber(self, num):
n = len(num)
for i, j in itertools.combinations(range(1, n), 2):
a, b = num[:i], num[i:j]
if b != str(int(b)):
continue
while j < n:
c = str(int(a) + int(b))
if not num.startswith(c, j):
break
j += len(c)
a, b = b, c
if j == n:
return True
return False
谢谢你,可爱的朋友。