Jobs

Interviews

Discussions

Additive Number

Medium

Asked by:

6 views

Topics:

StringsRecursion

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: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

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

Example 2:

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

Constraints:

1 <= num.length <= 35
num consists only of digits.

Follow up: How would you handle overflow for very large input integers?

Additive Number

Medium

Asked by:

6 views

Topics:

StringsRecursion

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: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

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

Example 2:

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

Constraints:

1 <= num.length <= 35
num consists only of digits.

Follow up: How would you handle overflow for very large input integers?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain leading zeros? If so, how should they be handled?
What is the maximum length of the input string?
If no additive sequence exists within the string, what should the function return?
Are the numbers in the additive sequence allowed to have leading zeros (e.g., "02" + "3" = "5")? Or can the first number in an additive sequence start with zero but must be represented as just a single zero?
Is it possible for the input string to be empty or null?

Brute Force Solution

Approach

The brute force approach for determining if a number is an additive number involves trying all possible starting numbers within the given string. We exhaustively check if the remaining digits can be formed by adding the previous two numbers. If any combination satisfies the additive property across the whole input number, we consider it a valid additive number.

Here's how the algorithm would work step-by-step:

First, pick the first number from the beginning of the given number string.
Then, pick the second number from the remaining part of the string.
Add these two numbers together to get a sum.
Check if the sum exists at the beginning of the remaining part of the string after picking the first two numbers. If the sum doesn't match or the sum is longer than what's left, this combination doesn't work.
If the sum matches, now use the second number and the sum as the new first and second numbers, and repeat adding them.
Continue checking if each new sum exists in the remaining digits of the original string.
If, at some point, the sum doesn't match, go back and try different sizes for the initial first and second numbers.
If you reach the end of the original string by successively adding numbers and matching their sums to the following digits, the original number is an additive number. Otherwise, keep trying other initial combinations.

Code Implementation

def is_additive_number(number_string):
    string_length = len(number_string)
    for first_number_length in range(1, (string_length // 2) + 1):
        for second_number_length in range(1, (string_length - first_number_length) // 2 + 1):
            first_number = number_string[:first_number_length]
            second_number = number_string[first_number_length:first_number_length + second_number_length]

            # Handle leading zeros; if so, this combination is invalid
            if (len(first_number) > 1 and first_number[0] == '0') or (len(second_number) > 1 and second_number[0] == '0'):
                continue

            remaining_string = number_string[first_number_length + second_number_length:]
            first_number_int = int(first_number)
            second_number_int = int(second_number)

            while remaining_string:
                sum_numbers = str(first_number_int + second_number_int)

                # Need to check if sum is a prefix of the remaining string
                if not remaining_string.startswith(sum_numbers):
                    break

                remaining_string = remaining_string[len(sum_numbers):]
                first_number_int = second_number_int
                second_number_int = int(sum_numbers)

            # If we've exhausted the string, then it's an additive number
            if not remaining_string:
                return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^3) – Let n be the length of the input string. We iterate through all possible lengths for the first number (up to n). Nested within this, we iterate through all possible lengths for the second number within the remaining string. For each pair of first and second numbers, we potentially build the additive sequence by repeatedly adding and comparing against the remaining part of the string which takes at most O(n) time since we are iterating at most n times to compare. Thus the overall time complexity approximates to O(n * n * n) which simplifies to O(n^3).

Space Complexity

O(N) – The primary space usage comes from the recursive calls needed to explore different additive number combinations. In the worst-case scenario, where no combination is initially valid and extensive backtracking occurs, the maximum depth of the recursion could be proportional to the length of the input string, N. Each recursive call requires storing local variables, leading to a stack space usage that is linearly dependent on N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

To determine if a number sequence is additive, we aim to efficiently verify if later parts of the sequence can be formed by adding earlier parts. This is done by intelligently testing possibilities to reduce unnecessary calculations. Instead of exhaustively checking every possible breakdown of the string, we use a directed approach to validate potential additive sequences.

Here's how the algorithm would work step-by-step:

Start by selecting the first two numbers from the beginning of the string. These will be the initial numbers in our potential additive sequence.
Calculate the sum of these two initial numbers.
Check if the sum appears at the correct position immediately after the initial two numbers in the string.
If the sum matches, update the sequence to include the sum as the next number.
Repeat the process by taking the last two numbers in the updated sequence, calculating their sum, and checking if the sum exists in the remaining part of the string.
Continue this process until you have examined the entire input string.
If you reach the end of the string and have always found matching sums, then the number sequence is additive.
If at any point the sum does not match the string, adjust the lengths of the initial two numbers and repeat the entire process from the beginning.
Because we start with smaller numbers and gradually increase them, we avoid unnecessary longer calculations and can confirm or deny the additive property of the sequence more efficiently.

Code Implementation

def isAdditiveNumber(number_string):
    string_length = len(number_string)
    for first_number_length in range(1, (string_length // 2) + 1):
        for second_number_length in range(1, (string_length - first_number_length) // 2 + 1 if string_length - first_number_length > 1 else string_length - first_number_length + 1):

            first_number = int(number_string[:first_number_length])
            second_number = int(number_string[first_number_length:first_number_length + second_number_length])
            remaining_string = number_string[first_number_length + second_number_length:]

            # Core logic: check if the remaining string forms an additive sequence.
            while remaining_string:
                expected_sum = str(first_number + second_number)
                if not remaining_string.startswith(expected_sum):
                    break

                remaining_string = remaining_string[len(expected_sum):]
                first_number = second_number
                second_number = int(expected_sum)
            
            # If remaining_string is empty, the entire string forms an additive sequence.
            if not remaining_string:
                return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^3) – Let n be the length of the input string. The algorithm iterates through all possible lengths for the first and second numbers in the additive sequence. This leads to a nested loop structure where the outer loop can iterate up to n times, and the inner loop can also iterate up to n times. Inside the inner loop, we perform string comparisons and additions, which take at most O(n) time in the worst case as the numbers involved grow in size up to the length of the input string. Therefore, the overall time complexity is approximately O(n * n * n) which simplifies to O(n^3).

Space Complexity

O(N) – The dominant space complexity arises from the implicit recursion depth when validating potential additive sequences. In the worst case, the algorithm might recursively call itself N times, where N is the length of the input string, as it checks for matching sums and extends the sequence. Each recursive call creates a new stack frame, leading to a maximum recursion depth of N. Therefore, the auxiliary space complexity is O(N) due to the call stack.

Edge Cases

Case	How to Handle
Empty string input	Return false immediately as an empty string cannot form an additive sequence.
String with length less than 3	Return false because an additive sequence requires at least three numbers.
Leading zeros in any number segment of the sequence	Reject sequences where numbers have leading zeros, except for zero itself.
Integer overflow when summing large numbers	Use a data type like `long` or handle large number addition using string manipulation to avoid overflow.
Very long input string causing performance issues	Implement backtracking with pruning to reduce the search space and avoid exponential time complexity.
Input string containing non-numeric characters	Return false if the string contains characters other than digits to prevent parsing errors.
Additive sequence starts with zero	Handle the cases where the sequence begins with '0' correctly, remembering that numbers other than '0' cannot start with leading zeros.
No valid additive sequence exists within the input string	Return false after exhaustively searching all possible partitions of the string and finding no valid sequence.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain leading zeros? If so, how should they be handled?
What is the maximum length of the input string?
If no additive sequence exists within the string, what should the function return?
Are the numbers in the additive sequence allowed to have leading zeros (e.g., "02" + "3" = "5")? Or can the first number in an additive sequence start with zero but must be represented as just a single zero?
Is it possible for the input string to be empty or null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, pick the first number from the beginning of the given number string.
Then, pick the second number from the remaining part of the string.
Add these two numbers together to get a sum.
Check if the sum exists at the beginning of the remaining part of the string after picking the first two numbers. If the sum doesn't match or the sum is longer than what's left, this combination doesn't work.
If the sum matches, now use the second number and the sum as the new first and second numbers, and repeat adding them.
Continue checking if each new sum exists in the remaining digits of the original string.
If, at some point, the sum doesn't match, go back and try different sizes for the initial first and second numbers.
If you reach the end of the original string by successively adding numbers and matching their sums to the following digits, the original number is an additive number. Otherwise, keep trying other initial combinations.

Code Implementation

def is_additive_number(number_string):
    string_length = len(number_string)
    for first_number_length in range(1, (string_length // 2) + 1):
        for second_number_length in range(1, (string_length - first_number_length) // 2 + 1):
            first_number = number_string[:first_number_length]
            second_number = number_string[first_number_length:first_number_length + second_number_length]

            # Handle leading zeros; if so, this combination is invalid
            if (len(first_number) > 1 and first_number[0] == '0') or (len(second_number) > 1 and second_number[0] == '0'):
                continue

            remaining_string = number_string[first_number_length + second_number_length:]
            first_number_int = int(first_number)
            second_number_int = int(second_number)

            while remaining_string:
                sum_numbers = str(first_number_int + second_number_int)

                # Need to check if sum is a prefix of the remaining string
                if not remaining_string.startswith(sum_numbers):
                    break

                remaining_string = remaining_string[len(sum_numbers):]
                first_number_int = second_number_int
                second_number_int = int(sum_numbers)

            # If we've exhausted the string, then it's an additive number
            if not remaining_string:
                return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by selecting the first two numbers from the beginning of the string. These will be the initial numbers in our potential additive sequence.
Calculate the sum of these two initial numbers.
Check if the sum appears at the correct position immediately after the initial two numbers in the string.
If the sum matches, update the sequence to include the sum as the next number.
Repeat the process by taking the last two numbers in the updated sequence, calculating their sum, and checking if the sum exists in the remaining part of the string.
Continue this process until you have examined the entire input string.
If you reach the end of the string and have always found matching sums, then the number sequence is additive.
If at any point the sum does not match the string, adjust the lengths of the initial two numbers and repeat the entire process from the beginning.
Because we start with smaller numbers and gradually increase them, we avoid unnecessary longer calculations and can confirm or deny the additive property of the sequence more efficiently.

Code Implementation

def isAdditiveNumber(number_string):
    string_length = len(number_string)
    for first_number_length in range(1, (string_length // 2) + 1):
        for second_number_length in range(1, (string_length - first_number_length) // 2 + 1 if string_length - first_number_length > 1 else string_length - first_number_length + 1):

            first_number = int(number_string[:first_number_length])
            second_number = int(number_string[first_number_length:first_number_length + second_number_length])
            remaining_string = number_string[first_number_length + second_number_length:]

            # Core logic: check if the remaining string forms an additive sequence.
            while remaining_string:
                expected_sum = str(first_number + second_number)
                if not remaining_string.startswith(expected_sum):
                    break

                remaining_string = remaining_string[len(expected_sum):]
                first_number = second_number
                second_number = int(expected_sum)
            
            # If remaining_string is empty, the entire string forms an additive sequence.
            if not remaining_string:
                return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return false immediately as an empty string cannot form an additive sequence.
String with length less than 3	Return false because an additive sequence requires at least three numbers.
Leading zeros in any number segment of the sequence	Reject sequences where numbers have leading zeros, except for zero itself.
Integer overflow when summing large numbers	Use a data type like `long` or handle large number addition using string manipulation to avoid overflow.
Very long input string causing performance issues	Implement backtracking with pruning to reduce the search space and avoid exponential time complexity.
Input string containing non-numeric characters	Return false if the string contains characters other than digits to prevent parsing errors.
Additive sequence starts with zero	Handle the cases where the sequence begins with '0' correctly, remembering that numbers other than '0' cannot start with leading zeros.
No valid additive sequence exists within the input string	Return false after exhaustively searching all possible partitions of the string and finding no valid sequence.