We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Additive Number

Difficulty: Medium

Problem Description

An additive number is a string whose digits can form an additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. Given a string containing only digits, return true if it is an additive number or false otherwise. Numbers in the additive sequence cannot have leading zeros.

Key Insights

  • The sequence must consist of at least three numbers.
  • Each number (after the first two) must be the sum of the previous two numbers.
  • Leading zeros are not allowed, which means a number like "01" or "001" is invalid.
  • The problem can be approached using backtracking to explore different combinations of the first two numbers.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the input string. Each pair of starting numbers can lead to multiple recursive checks. Space Complexity: O(n), for the recursion stack space in the worst case.

Solution

To determine if a string can form an additive sequence, we can use a backtracking approach. The idea is to try different pairs of starting numbers from the string and recursively check if the remaining part of the string can be split into valid numbers according to the additive sequence rules.

  1. Iterate through the string to select the first number.
  2. For each choice of the first number, select a second number from the remaining substring.
  3. Calculate the expected next number by summing the two chosen numbers and check if it matches the next part of the string.
  4. If it matches, continue the process with the new numbers until the entire string is consumed.

This approach ensures that all possible pairs of starting numbers are checked while adhering to the constraints of the problem.

Code Solutions

def isAdditiveNumber(num: str) -> bool:
    def isValid(first: str, second: str, remaining: str) -> bool:
        if not remaining:
            return True
        # Calculate the expected next number in the sequence
        expected = str(int(first) + int(second))
        # Check if the remaining string starts with the expected number
        if remaining.startswith(expected):
            return isValid(second, expected, remaining[len(expected):])
        return False
    
    n = len(num)
    # Try every possible split of the first two numbers
    for i in range(1, n):
        for j in range(i + 1, n):
            first, second = num[:i], num[i:j]
            # Check for leading zeros
            if (len(first) > 1 and first[0] == '0') or (len(second) > 1 and second[0] == '0'):
                continue
            remaining = num[j:]
            if isValid(first, second, remaining):
                return True
    return False
← Back to All Questions