algoadvance

LeetCode 306: Additive Number

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.

Note:

Example:

Input: "112358"
Output: True
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Input: "199100199"
Output: True
Explanation: The additive sequence is: 1, 99, 100, 199.
             1 + 99 = 100, 99 + 100 = 199

Clarifying Questions

  1. Input Constraints: What is the maximum length of the input string?
    • Typically, this is not specified, but we will assume the constraints of typical LeetCode problems, e.g., (10^4).
  2. Validations: Should we handle invalid input or non-digit characters in the input string?
    • The problem indicates the string contains only digits so no need to handle invalid input types.
  3. Leading Zeros: Can we have numbers other than 0 with leading zeros?
    • No, numbers other than 0 cannot have leading zeros.

Strategy

  1. Initial Checks:
    • Ensure the string length is at least 3 because the sequence should contain at least three numbers.
  2. Two Pointers: Fix the first two numbers using two nested loops.
    • Iterate over all possible starting numbers (num1) and (num2) within the constraints of leading zero rules.
  3. Validation:
    • Generate the remaining sequence and check if it matches the input string.
    • This involves iterating through the rest of the string, validating that subsequent numbers match the addition property of the previous two numbers.
  4. Edge Cases: Handle cases where there might be leading zeros.

Code

def is_additive_number(num: str) -> bool:
    n = num.length()

    # Try every combination for the first two numbers
    for i in range(1, n):  # first number ends at i-1
        for j in range(i + 1, n):  # second number ends at j-1
            
            # Lets follow the constraints: No leading zeros unless the number is 0
            if (num[0] == '0' and i > 1) or (num[i] == '0' and j > i + 1):
                continue
            
            num1 = int(num[0:i])
            num2 = int(num[i:j])
            
            k = j  # start of the next number
            while k < n:
                num3 = num1 + num2
                num3_str = str(num3)
                if not num.startswith(num3_str, k):
                    break
                
                # Move to the next sequence
                k += len(num3_str)
                num1, num2 = num2, num3
            
            if k == n:
                return True
                
    return False

# Examples
print(is_additive_number("112358"))  # True
print(is_additive_number("199100199"))  # True

Time Complexity

Thus, the overall time complexity is (O(n^3)).

This should work efficiently with the constraints of typical LeetCode problem sizes.

Try our interview co-pilot at AlgoAdvance.com