# 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: | Rule | Meaning | |---|---| | At least three numbers | We need `a, b, c`, not only `a, b` | | Sum rule | Every number after the first two equals the sum of the previous two | | No leading zeros | Numbers like `"03"` and `"012"` are invalid | For example, `"112358"` is valid because it can be split as: ```text 1, 1, 2, 3, 5, 8 ``` and: ```text 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 | Item | Meaning | |---|---| | Input | A digit string `num` | | Output | `true` if `num` can form an additive sequence, otherwise `false` | | Constraint | `1 <= num.length <= 35` | | Digits only | `num` contains only characters `'0'` through `'9'` | Function shape: ```python def isAdditiveNumber(num: str) -> bool: ... ``` ## Examples Example 1: ```python num = "112358" ``` Output: ```python True ``` Valid split: ```text 1, 1, 2, 3, 5, 8 ``` Example 2: ```python num = "199100199" ``` Output: ```python True ``` Valid split: ```text 1, 99, 100, 199 ``` because: ```text 1 + 99 = 100 99 + 100 = 199 ``` Example 3: ```python num = "1023" ``` Output: ```python False ``` One tempting split is: ```text 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: ```python a = 1 b = 99 ``` then the next number must be: ```python a + b = 100 ``` After that, the next number must be: ```python 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: ```text 0 ``` Invalid: ```text 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 | Metric | Value | Why | |---|---:|---| | Time | `O(n^3)` | There are `O(n^2)` first-two splits, and each verification can scan up to `O(n)` characters | | Space | `O(n)` | String forms of generated sums can have length up to `n` | For `n <= 35`, this is easily fast enough. ## Implementation ```python 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: ```python n = len(num) ``` The helper for leading zeros is: ```python 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. ```python def valid_from(first: int, second: int, start: int) -> bool: ``` At each step, the next number is forced: ```python third = first + second third_str = str(third) ``` Then we check whether the remaining string starts with that sum. ```python if not num.startswith(third_str, start): return False ``` If it matches, move the index forward. ```python start += len(third_str) ``` Then shift the last two numbers: ```python first = second second = third ``` If we consume the whole string, the split is valid. ```python return count >= 3 ``` Now the outer loops choose the first two numbers. ```python 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. ```python if has_leading_zero(first_str): break ``` Then choose the second number. ```python 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. ```python if has_leading_zero(second_str): break ``` If the deterministic check succeeds, return `True`. ```python if valid_from(first, second, j): return True ``` If every split fails, return `False`. ## Testing ```python 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: | Test | Why | |---|---| | `"112358"` | Classic additive sequence | | `"199100199"` | Multi-digit numbers | | `"1023"` | Leading-zero rejection | | `"000"` | Valid sequence `0, 0, 0` | | `"101"` | Valid sequence `1, 0, 1` | | `"1203"` | Rejects invalid continuation | | `"12122436"` | Valid sequence `12, 12, 24, 36` | | `"123"` | Minimum valid additive length | | `"12"` | Too short to form three numbers |