306. Additive Number

Description

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.

Intuition

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.

Approach

1. Iterate Over Possible Splits: - Loop through all possible starting pairs of numbers by splitting the string into three parts: the first number (f), the second number (s), and the remaining string (l).
2. Validation: - For each split, first check if the first two numbers (f and s) are valid. A number is considered valid if it does not have leading zeros unless it's "0". - Use a recursive function to validate if the rest of the string (l) can be split into a sequence where each subsequent number is the sum of the previous two numbers.
3. Recursive Validation: - If the current sum of 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.
4. Edge Cases: - Handle edge cases where the number string is too short to form a sequence or contains leading zeros, which are not allowed unless the number is "0".

Complexity

Time Complexity:

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.

Space Complexity:

The space complexity is (O(n)) due to the recursive call stack and the space required to store intermediate substrings.

Code

C++

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int n = num.length();

        auto isValid = [](const string &str) {
            return str.length() == 1 || str[0] != '0';
        };

        function 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;
    }
};

Python

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

Java

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()));
    }
}

JavaScript

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
};