LeetCode 306: Additive Number

Problem Restatement

We are given a string num containing only digits.

Return true if the digits can be split into an additive sequence. Otherwise, return false.

An additive sequence must satisfy three rules:

For example, "112358" is valid because it can be split as:

1, 1, 2, 3, 5, 8

and:

1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8

The official statement says the input length is at most 35, and the follow-up asks how to handle overflow for very large integers. Python integers already handle arbitrary precision.

Input and Output

Function shape:

def isAdditiveNumber(num: str) -> bool:
    ...

Examples

Example 1:

num = "112358"

Output:

True

Valid split:

1, 1, 2, 3, 5, 8

Example 2:

num = "199100199"

Output:

True

Valid split:

1, 99, 100, 199

because:

1 + 99 = 100
99 + 100 = 199

Example 3:

num = "1023"

Output:

False

One tempting split is:

1, 02, 3

But "02" has a leading zero, so it is invalid.

First Thought: Try Every Split

We could try to split the string into every possible list of numbers.

For each split, check whether the sequence is additive.

But this creates too many possibilities because every gap between two digits can either be a cut or not a cut.

For a string of length n, there are many possible partitions.

We need a smaller search.

Key Insight

Once we choose the first two numbers, the rest of the sequence is forced.

If the first two numbers are:

a = 1
b = 99

then the next number must be:

a + b = 100

After that, the next number must be:

99 + 100 = 199

So we only need to enumerate the first two numbers.

After choosing them, we scan the rest of the string deterministically.

Handling Leading Zeros

A number can be exactly "0".

But a multi-digit number cannot start with "0".

Valid:

0

Invalid:

01
00
012

So when choosing the first number or second number, we stop if that substring has a leading zero.

The same rule is automatically handled for later numbers because later numbers are generated by addition and converted to normal decimal strings.

Algorithm

Let n = len(num).

Try every possible end position for the first number.

Then try every possible end position for the second number.

For each pair:

1. Reject the first number if it has a leading zero.
2. Reject the second number if it has a leading zero.
3. Convert both numbers to integers.
4. Starting after the second number, repeatedly:
   • Compute next_value = first + second.
   • Convert it to a string.
   • Check whether the remaining input starts with that string.
   • If not, this split fails.
   • Move forward and update the pair.
5. If we consume the whole string and used at least three numbers, return True.

If no split works, return False.

Correctness

The algorithm checks every valid choice of the first number and second number.

For any additive sequence, the first two numbers uniquely determine every later number because each later number must be the sum of the previous two.

So when the algorithm tests the correct first two numbers, the deterministic checking step must follow exactly the same sequence. Each generated sum must match the next digits of num.

If the algorithm consumes the whole string, then the string has been split into at least three numbers, and every number after the first two equals the sum of the previous two. The leading-zero checks guarantee that all numbers have valid decimal representation.

If the algorithm returns False, then every possible first-two-number split failed. Since every additive sequence must have some first two numbers, no valid additive sequence exists.

Therefore, the algorithm is correct.

Complexity

For n <= 35, this is easily fast enough.

Implementation

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

        def has_leading_zero(s: str) -> bool:
            return len(s) > 1 and s[0] == "0"

        def valid_from(first: int, second: int, start: int) -> bool:
            count = 2

            while start < n:
                third = first + second
                third_str = str(third)

                if not num.startswith(third_str, start):
                    return False

                start += len(third_str)
                first = second
                second = third
                count += 1

            return count >= 3

        for i in range(1, n):
            first_str = num[:i]

            if has_leading_zero(first_str):
                break

            for j in range(i + 1, n):
                second_str = num[i:j]

                if has_leading_zero(second_str):
                    break

                first = int(first_str)
                second = int(second_str)

                if valid_from(first, second, j):
                    return True

        return False

Code Explanation

We store the length:

n = len(num)

The helper for leading zeros is:

def has_leading_zero(s: str) -> bool:
    return len(s) > 1 and s[0] == "0"

This allows "0" but rejects "01".

The main verifier starts with two chosen numbers and a string index.

def valid_from(first: int, second: int, start: int) -> bool:

At each step, the next number is forced:

third = first + second
third_str = str(third)

Then we check whether the remaining string starts with that sum.

if not num.startswith(third_str, start):
    return False

If it matches, move the index forward.

start += len(third_str)

Then shift the last two numbers:

first = second
second = third

If we consume the whole string, the split is valid.

return count >= 3

Now the outer loops choose the first two numbers.

for i in range(1, n):
    first_str = num[:i]

i is the end of the first number.

If the first number has a leading zero, longer first numbers will also have a leading zero, so we stop.

if has_leading_zero(first_str):
    break

Then choose the second number.

for j in range(i + 1, n):
    second_str = num[i:j]

If the second number has a leading zero, longer second numbers starting at the same place will also be invalid, so we stop that inner loop.

if has_leading_zero(second_str):
    break

If the deterministic check succeeds, return True.

if valid_from(first, second, j):
    return True

If every split fails, return False.

Testing

def run_tests():
    s = Solution()

    assert s.isAdditiveNumber("112358") is True
    assert s.isAdditiveNumber("199100199") is True
    assert s.isAdditiveNumber("1023") is False
    assert s.isAdditiveNumber("000") is True
    assert s.isAdditiveNumber("101") is True
    assert s.isAdditiveNumber("1203") is False
    assert s.isAdditiveNumber("12122436") is True
    assert s.isAdditiveNumber("123") is True
    assert s.isAdditiveNumber("12") is False

    print("all tests passed")

run_tests()

Test meaning: