Additive Number

Problem#

Return true iff num (digit string) is an additive sequence: at least 3 numbers, each (after the first two) equals the sum of the previous two. Leading zeros disallowed (except for "0" itself).

Examples#

"112358" → true (1+1=2, 1+2=3, 2+3=5, 3+5=8)
"199100199" → true

Approach#

Try every pair of starting summand lengths (len1, len2). Validate they don’t have leading zeros, then greedily extend by computing the next number = a + b until either matching the next substring or failing.

Solution#

class Solution {
public:
    bool isAdditiveNumber(string num) {
        int n = num.size();
        auto noLeadingZero = [&](int start, int len) {
            return len == 1 || num[start] != '0';
        };
        auto add = [](const string& a, const string& b) {
            string s; int carry = 0, i = a.size() - 1, j = b.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int x = (i >= 0 ? a[i--] - '0' : 0) + (j >= 0 ? b[j--] - '0' : 0) + carry;
                s += '0' + x % 10;
                carry = x / 10;
            }
            reverse(s.begin(), s.end());
            return s;
        };
        for (int l1 = 1; l1 <= n / 2; ++l1) {
            if (!noLeadingZero(0, l1)) break;
            for (int l2 = 1; max(l1, l2) <= n - l1 - l2; ++l2) {
                if (!noLeadingZero(l1, l2)) break;
                string a = num.substr(0, l1), b = num.substr(l1, l2);
                int pos = l1 + l2;
                bool ok = true;
                while (pos < n) {
                    string c = add(a, b);
                    if (pos + (int)c.size() > n || num.substr(pos, c.size()) != c) { ok = false; break; }
                    pos += c.size();
                    a = b; b = c;
                }
                if (ok && pos == n) return true;
            }
        }
        return false;
    }
};

func isAdditiveNumber(num string) bool {
    n := len(num)
    noLeadingZero := func(start, length int) bool {
        return length == 1 || num[start] != '0'
    }
    add := func(a, b string) string {
        s := []byte{}
        carry, i, j := 0, len(a)-1, len(b)-1
        for i >= 0 || j >= 0 || carry > 0 {
            x := 0
            if i >= 0 {
                x = int(a[i] - '0')
                i--
            }
            y := 0
            if j >= 0 {
                y = int(b[j] - '0')
                j--
            }
            v := x + y + carry
            s = append(s, byte('0'+v%10))
            carry = v / 10
        }
        for l, r := 0, len(s)-1; l < r; l, r = l+1, r-1 {
            s[l], s[r] = s[r], s[l]
        }
        return string(s)
    }
    for l1 := 1; l1 <= n/2; l1++ {
        if !noLeadingZero(0, l1) {
            break
        }
        for l2 := 1; max(l1, l2) <= n-l1-l2; l2++ {
            if !noLeadingZero(l1, l2) {
                break
            }
            a, b := num[:l1], num[l1:l1+l2]
            pos := l1 + l2
            ok := true
            for pos < n {
                c := add(a, b)
                if pos+len(c) > n || num[pos:pos+len(c)] != c {
                    ok = false
                    break
                }
                pos += len(c)
                a, b = b, c
            }
            if ok && pos == n {
                return true
            }
        }
    }
    return false
}

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)

        def no_leading_zero(start: int, length: int) -> bool:
            return length == 1 or num[start] != '0'

        for l1 in range(1, n // 2 + 1):
            if not no_leading_zero(0, l1):
                break
            l2 = 1
            while max(l1, l2) <= n - l1 - l2:
                if not no_leading_zero(l1, l2):
                    break
                a, b = num[:l1], num[l1:l1 + l2]
                pos = l1 + l2
                ok = True
                while pos < n:
                    c = str(int(a) + int(b))
                    if pos + len(c) > n or num[pos:pos + len(c)] != c:
                        ok = False
                        break
                    pos += len(c)
                    a, b = b, c
                if ok and pos == n:
                    return True
                l2 += 1
        return False

var isAdditiveNumber = function(num) {
    const n = num.length;
    const noLeadingZero = (start, len) => len === 1 || num[start] !== '0';
    const add = (a, b) => {
        const s = [];
        let carry = 0, i = a.length - 1, j = b.length - 1;
        while (i >= 0 || j >= 0 || carry) {
            const x = (i >= 0 ? a.charCodeAt(i--) - 48 : 0) + (j >= 0 ? b.charCodeAt(j--) - 48 : 0) + carry;
            s.push(String(x % 10));
            carry = Math.floor(x / 10);
        }
        return s.reverse().join('');
    };
    for (let l1 = 1; l1 <= Math.floor(n / 2); l1++) {
        if (!noLeadingZero(0, l1)) break;
        for (let l2 = 1; Math.max(l1, l2) <= n - l1 - l2; l2++) {
            if (!noLeadingZero(l1, l2)) break;
            let a = num.slice(0, l1), b = num.slice(l1, l1 + l2);
            let pos = l1 + l2;
            let ok = true;
            while (pos < n) {
                const c = add(a, b);
                if (pos + c.length > n || num.slice(pos, pos + c.length) !== c) { ok = false; break; }
                pos += c.length;
                a = b;
                b = c;
            }
            if (ok && pos === n) return true;
        }
    }
    return false;
};

class Solution {
    private String num;

    private boolean noLeadingZero(int start, int len) {
        return len == 1 || num.charAt(start) != '0';
    }

    private String add(String a, String b) {
        StringBuilder s = new StringBuilder();
        int carry = 0, i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0 || carry > 0) {
            int x = i >= 0 ? a.charAt(i--) - '0' : 0;
            int y = j >= 0 ? b.charAt(j--) - '0' : 0;
            int v = x + y + carry;
            s.append((char) ('0' + v % 10));
            carry = v / 10;
        }
        return s.reverse().toString();
    }

    public boolean isAdditiveNumber(String num) {
        this.num = num;
        int n = num.length();
        for (int l1 = 1; l1 <= n / 2; l1++) {
            if (!noLeadingZero(0, l1)) break;
            for (int l2 = 1; Math.max(l1, l2) <= n - l1 - l2; l2++) {
                if (!noLeadingZero(l1, l2)) break;
                String a = num.substring(0, l1);
                String b = num.substring(l1, l1 + l2);
                int pos = l1 + l2;
                boolean ok = true;
                while (pos < n) {
                    String c = add(a, b);
                    if (pos + c.length() > n || !num.substring(pos, pos + c.length()).equals(c)) {
                        ok = false;
                        break;
                    }
                    pos += c.length();
                    a = b;
                    b = c;
                }
                if (ok && pos == n) return true;
            }
        }
        return false;
    }
}

function isAdditiveNumber(num: string): boolean {
    const n = num.length;
    const noLeadingZero = (start: number, len: number): boolean => len === 1 || num[start] !== '0';
    const add = (a: string, b: string): string => {
        const s: string[] = [];
        let carry = 0, i = a.length - 1, j = b.length - 1;
        while (i >= 0 || j >= 0 || carry) {
            const x = (i >= 0 ? a.charCodeAt(i--) - 48 : 0) + (j >= 0 ? b.charCodeAt(j--) - 48 : 0) + carry;
            s.push(String(x % 10));
            carry = Math.floor(x / 10);
        }
        return s.reverse().join('');
    };
    for (let l1 = 1; l1 <= Math.floor(n / 2); l1++) {
        if (!noLeadingZero(0, l1)) break;
        for (let l2 = 1; Math.max(l1, l2) <= n - l1 - l2; l2++) {
            if (!noLeadingZero(l1, l2)) break;
            let a = num.slice(0, l1), b = num.slice(l1, l1 + l2);
            let pos = l1 + l2;
            let ok = true;
            while (pos < n) {
                const c = add(a, b);
                if (pos + c.length > n || num.slice(pos, pos + c.length) !== c) { ok = false; break; }
                pos += c.length;
                a = b;
                b = c;
            }
            if (ok && pos === n) return true;
        }
    }
    return false;
}

Editorial#

Strings (not ints) for the running numbers handle arbitrary precision. Two nested loops choose the prefix lengths; the inner greedy verifies. The leading-zero rule trims the search early.

Complexity#

Time: O(n³).
Space: O(n).

Problem#

Examples#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#