Dare2Solve
The isAdditiveNumber
problem requires determining whether a given string representing a number can be split into a sequence of at least three positive numbers where each number is the sum of the two preceding ones. The function must return true
if such a sequence exists, and false
otherwise.
An additive number sequence follows the property where each number in the sequence (starting from the third) is the sum of the two preceding numbers. The challenge is to find a valid partition of the string such that the sequence adheres to this property. A brute-force approach of testing all possible partitions and validating them can be optimized using recursion.
Iterate Over Possible Splits:
f
), the second number (s
), and the remaining string (l
).Validation:
f
and s
) are valid. A number is considered valid if it does not have leading zeros unless it's "0".l
) can be split into a sequence where each subsequent number is the sum of the previous two numbers.Recursive Validation:
f
and s
matches the beginning of l
, continue the sequence by updating f
and s
and slicing l
accordingly. If l
is empty, the sequence is valid.Edge Cases:
The time complexity is approximately (O(n^3)), where (n) is the length of the string. This arises from the nested loops that consider every possible pair of first and second numbers and the recursive checks.
The space complexity is (O(n)) due to the recursive call stack and the space required to store intermediate substrings.
class Solution {
public:
bool isAdditiveNumber(string num) {
int n = num.length();
auto isValid = [](const string &str) {
return str.length() == 1 || str[0] != '0';
};
function<bool(string, string, string)> validSeq = [&](string f, string s, string l) {
if (l.length() == 0) return true;
string sum = to_string(stoll(f) + stoll(s));
if (l.substr(0, sum.length()) != sum) return false;
return validSeq(s, sum, l.substr(sum.length()));
};
for (int i = 1; i <= n / 2; i++) {
for (int j = i + 1; j <= n - i; j++) {
string f = num.substr(0, i);
string s = num.substr(i, j - i);
string l = num.substr(j);
if (isValid(f) && isValid(s) && validSeq(f, s, l))
return true;
}
}
return false;
}
};
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
def isValid(s: str) -> bool:
return len(s) == 1 or s[0] != '0'
def validSeq(f: str, s: str, l: str) -> bool:
if len(l) == 0:
return True
sum_str = str(int(f) + int(s))
if not l.startswith(sum_str):
return False
return validSeq(s, sum_str, l[len(sum_str):])
n = len(num)
for i in range(1, n // 2 + 1):
for j in range(i + 1, n - i + 1):
f, s, l = num[:i], num[i:j], num[j:]
if isValid(f) and isValid(s) and validSeq(f, s, l):
return True
return False
public class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i <= n / 2; i++) {
for (int j = i + 1; j <= n - i; j++) {
String f = num.substring(0, i);
String s = num.substring(i, j);
String l = num.substring(j);
if (isValid(f) && isValid(s) && validSeq(f, s, l)) {
return true;
}
}
}
return false;
}
private boolean isValid(String str) {
return str.length() == 1 || str.charAt(0) != '0';
}
private boolean validSeq(String f, String s, String l) {
if (l.length() == 0) return true;
String sum = String.valueOf(Long.parseLong(f) + Long.parseLong(s));
if (!l.startsWith(sum)) return false;
return validSeq(s, sum, l.substring(sum.length()));
}
}
var isAdditiveNumber = function (num) {
const n = num.length
const isValid = (str) => {
return str.length === 1 || str[0] !== '0'
}
const validSeq = (f, s, l) => {
if (l.length === 0) return true
let sum = (parseInt(f) + parseInt(s)).toString();
for (let c = 0; c < sum.length; c++) if (sum[c] !== l[c]) return false
return validSeq(s, sum, l.slice(sum.length))
}
for (let i = 1; i <= Math.floor(n / 2); i++) {
for (let j = i + 1; j <= n - i; j++) {
let f = num.slice(0, i), s = num.slice(i, j), l = num.slice(j);
if (isValid(f) && isValid(s) && validSeq(f, s, l))
return true
}
}
return false
};