Af first I read the title as "Addictive Number". Anyway, this problem can be solved elegantly using recursion. This post shares a nice recursive C++ code with handling of the follow-up by implementing string addition function.
The code is rewritten as follows.
class Solution {
public:
bool isAdditiveNumber(string num) {
int n = num.size();
for (int i = ; i <= n/; i++)
for (int j = ; j <= (n-i)/; j++)
if (additive(num.substr(, i), num.substr(i, j), num.substr(i + j)))
return true;
return false;
}
private:
bool additive(string a, string b, string c) {
string s = add(a, b);
if (s == c) return true;
if (c.size() <= s.size() || s.compare(c.substr(, s.size())))
return false;
return additive(b, s, c.substr(s.size()));
}
string add(string& a, string& b) {
string s;
int i = a.size() - , j = b.size() - , c = ;
while (i >= || j >= ) {
int d = (i >= ? (a[i--] - '') : ) + (j >= ? (b[j--] - '') : ) + c;
s += (d % + '');
c = d / ;
}
if (c) s += ('' + c);
reverse(s.begin(), s.end());
return s;
}
};
This problem can also be solved iteratively, like peisi's code, which is rewritten in C++ below.
class Solution {
public:
bool isAdditiveNumber(string num) {
int n = num.length();
for (int i = ; i <= n/; i++)
for (int j = ; max(i, j) <= n - i - j; j++)
if (additive(i, j, num)) return true;
return false;
}
private:
bool additive(int i, int j, string& num) {
if (num[i] == '' && j > ) return false;
string a = num.substr(, i);
string b = num.substr(i, j);
for (int k = i + j; k < num.length(); k += b.length()) {
b.swap(a);
b = add(a, b);
string tail = num.substr(k);
if (b.compare(tail.substr(, b.size()))) return false;
}
return true;
}
string add(string& a, string& b) {
string s;
int i = a.size() - , j = b.size() - , c = ;
while (i >= || j >= ) {
int d = (i >= ? (a[i--] - '') : ) + (j >= ? (b[j--] - '') : ) + c;
s += (d % + '');
c = d / ;
}
if (c) s += ('' + c);
reverse(s.begin(), s.end());
return s;
}
};
If you are a Pythoner, you may also love Stefan's code, which is pasted below.
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