Additive Number

Med

#0293Time: O(n^3). The nested loops to pick the first two numbers have a complexity of `O(n^2)`. For each pair, the `checkSequence` function is called. The work done in one full path of `checkSequence` involves a series of string additions and comparisons. The total work is proportional to the sum of lengths of all numbers, which is `O(n)`. Thus, the validation for one pair is `O(n)`. Total complexity is `O(n^2) * O(n) = O(n^3)`.Space: O(n). The space is dominated by the recursion stack depth of `checkSequence`, which can be at most `O(n)` (in the case of a sequence like "101123..."). The strings created during the process also contribute `O(n)` space.1 company

Patterns

Backtracking

Data structures

String

Companies

Epic Systems

Prompt

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?

Approaches

2 approaches with complexity analysis and trade-offs.

A much more efficient approach is to realize that an additive sequence is uniquely determined by its first two numbers. We can iterate through all possible first and second numbers, and for each pair, check if they can form a valid additive sequence that consumes the entire input string.

Algorithm

1. The main function isAdditiveNumber iterates through all possible lengths, i and j, for the first two numbers.
1. The loop for i (length of the first number) runs from 1 to n/2.
1. The loop for j (length of the second number) runs from 1 up to the point where the remaining string length n-i-j is at least max(i, j).
1. Inside the loops, extract the first two number strings, s1 and s2.
1. Check for invalid leading zeros. If s1 has a leading zero (and length > 1), we can break the outer loop. If s2 has one, continue to the next j.
1. Call a recursive helper function, checkSequence(s1, s2, rest_of_string), to validate the remainder of the string.
1. The checkSequence function is the core of the backtracking:
- a. Base Case: If the remaining string is empty, it means the whole string was consumed by a valid sequence, so return true.
- b. Calculate the sum of the two previous numbers using a stringAdd helper.
- c. Check if the remaining string starts with the calculated sum string. If not, return false.
- d. If it does, make a recursive call with the next set of numbers: checkSequence(s2, sum, rest.substring(sum.length())).
1. If checkSequence returns true at any point, the main function returns true.
1. If the loops complete without finding a solution, return false.

Walkthrough

We use two nested loops to select the first two numbers, num1 and num2. The outer loop determines the length of num1, and the inner loop determines the length of num2. Some optimizations can be applied to the loop bounds. For instance, the length of the first or second number cannot be more than half the total string length, because the third number must be at least as long as the longer of the first two.

After selecting num1 and num2, we start a validation process. This process recursively or iteratively generates the next number in the sequence (sum = num1 + num2) and checks if the remaining input string starts with this sum. If it does, we continue the process with num2 and sum. If at any point the check fails, or if we successfully consume the entire string, the process terminates.

Since the numbers can be very large (up to 35 digits), we cannot use standard integer types like long. Instead, we must represent numbers as strings and implement a string addition helper function to handle the 'Follow up' part of the problem.

1class Solution {2    public boolean isAdditiveNumber(String num) {3        int n = num.length();4        if (n < 3) return false;5 6        // i is the length of the first number7        for (int i = 1; i <= n / 2; ++i) {8            // j is the length of the second number9            // The third number's length must be >= max(i, j).10            // So, n - i - j >= max(i, j).11            for (int j = 1; Math.max(i, j) <= n - i - j; ++j) {12                if (isValid(i, j, num)) {13                    return true;14                }15            }16        }17        return false;18    }19 20    // Checks if a valid sequence can be formed starting with numbers of length i and j21    private boolean isValid(int i, int j, String num) {22        String s1 = num.substring(0, i);23        String s2 = num.substring(i, i + j);24 25        // Rule: no leading zeros, unless the number is "0" itself.26        if (s1.length() > 1 && s1.charAt(0) == '0') return false;27        if (s2.length() > 1 && s2.charAt(0) == '0') return false;28 29        String rest = num.substring(i + j);30        return checkSequence(s1, s2, rest);31    }32 33    // Recursively checks if the 'rest' of the string follows the additive sequence34    private boolean checkSequence(String prev1, String prev2, String rest) {35        if (rest.isEmpty()) {36            return true; // The entire string has been consumed by the sequence37        }38 39        String sum = stringAdd(prev1, prev2);40        if (!rest.startsWith(sum)) {41            return false; // The next number in the string doesn't match the sum42        }43 44        // Recurse with the next pair of numbers45        return checkSequence(prev2, sum, rest.substring(sum.length()));46    }47 48    // Helper function to add two numbers represented as strings49    private String stringAdd(String n1, String n2) {50        StringBuilder res = new StringBuilder();51        int i = n1.length() - 1;52        int j = n2.length() - 1;53        int carry = 0;54        while (i >= 0 || j >= 0 || carry != 0) {55            int digit1 = i >= 0 ? n1.charAt(i--) - '0' : 0;56            int digit2 = j >= 0 ? n2.charAt(j--) - '0' : 0;57            int sum = digit1 + digit2 + carry;58            res.append(sum % 10);59            carry = sum / 10;60        }61        return res.reverse().toString();62    }63}

Complexity

Time

O(n^3). The nested loops to pick the first two numbers have a complexity of `O(n^2)`. For each pair, the `checkSequence` function is called. The work done in one full path of `checkSequence` involves a series of string additions and comparisons. The total work is proportional to the sum of lengths of all numbers, which is `O(n)`. Thus, the validation for one pair is `O(n)`. Total complexity is `O(n^2) * O(n) = O(n^3)`.

Space

O(n). The space is dominated by the recursion stack depth of `checkSequence`, which can be at most `O(n)` (in the case of a sequence like "101123..."). The strings created during the process also contribute `O(n)` space.

Trade-offs

Pros

Significantly more efficient than brute-forcing all partitions.
Passes within the time limits for the given constraints.
The logic is a direct and structured way to search for the solution.

Cons

The complexity is polynomial, which might be slow for very large n (though n=35 is fine).
Requires careful implementation of string addition and handling of edge cases like leading zeros.

This is a highly inefficient approach that explores every possible way to partition the input string into a sequence of numbers. For each partition, it checks if the sequence is additive. This method is primarily for demonstrating a naive solution and understanding the problem space.

Algorithm

1. Define a recursive function find(index, partition) to generate all possible partitions of the input string num.
1. The base case for the recursion is when index reaches the end of the string. At this point, a complete partition has been formed.
1. Once a partition is formed, check if it represents a valid additive sequence. A sequence is additive if it has at least three numbers and each number after the second is the sum of the two preceding ones.
1. In the recursive step, loop from k = index to n-1 to form the next number in the partition, s = num.substring(index, k+1).
1. Handle leading zeros: if s has more than one digit and starts with '0', it's an invalid number, so this path is pruned.
1. Add the valid number s to the current partition and make a recursive call: find(k+1, partition). After the call returns, backtrack by removing s to explore other possibilities.
1. The validation function, say isAdditive(partition), will use a string addition helper to verify the sum property.
1. If any partition is found to be a valid additive sequence, the main function returns true immediately. If all partitions are explored without success, it returns false.

Walkthrough

The core idea is to use recursion or backtracking to generate all 2^(n-1) possible partitions of the string. A function generate(index, current_partition) would try to form a number starting at index and ending at k (where k goes from index to n-1). For each number formed, it's added to current_partition, and the function recurses from k+1. When a full partition is formed (i.e., index == n), it's validated. The validation step checks if it's an additive sequence with at least three numbers, where each number after the second is the sum of the two preceding ones. Due to the large number of possible partitions, this approach is not feasible for the given constraints.

Complexity

Time

O(2^n * n). The number of ways to partition a string of length `n` is `2^(n-1)`. Validating each partition takes `O(n)` time, as it involves string additions and comparisons over the length of the string.

Space

O(n). The recursion depth can go up to `n`, and the list storing the current partition can also take `O(n)` space.

Trade-offs

Pros

Conceptually simple to understand as it directly models the problem of finding a valid partition.

Cons

Extremely slow due to its exponential time complexity.
Impractical for the given constraints (n <= 35) and will time out.

Solutions

Solution

1class Solution { public boolean isAdditiveNumber ( String num ) { int n = num . length (); for ( int i = 1 ; i < Math . min ( n - 1 , 19 ); ++ i ) { for ( int j = i + 1 ; j < Math . min ( n , i + 19 ); ++ j ) { if ( i > 1 && num . charAt ( 0 ) == '0' ) { break ; } if ( j - i > 1 && num . charAt ( i ) == '0' ) { continue ; } long a = Long . parseLong ( num . substring ( 0 , i )); long b = Long . parseLong ( num . substring ( i , j )); if ( dfs ( a , b , num . substring ( j ))) { return true ; } } } return false ; } private boolean dfs ( long a , long b , String num ) { if ( "" . equals ( num )) { return true ; } if ( a + b > 0 && num . charAt ( 0 ) == '0' ) { return false ; } for ( int i = 1 ; i < Math . min ( num . length () + 1 , 19 ); ++ i ) { if ( a + b == Long . parseLong ( num . substring ( 0 , i ))) { if ( dfs ( b , a + b , num . substring ( i ))) { return true ; } } } return false ; } }

1class Solution { public: bool isAdditiveNumber ( string num ) { int n = num . size (); for ( int i = 1 ; i < min ( n - 1 , 19 ); ++ i ) { for ( int j = i + 1 ; j < min ( n , i + 19 ); ++ j ) { if ( i > 1 && num [ 0 ] == '0' ) break ; if ( j - i > 1 && num [ i ] == '0' ) continue ; auto a = stoll ( num . substr ( 0 , i )); auto b = stoll ( num . substr ( i , j - i )); if ( dfs ( a , b , num . substr ( j , n - j ))) return true ; } } return false ; } bool dfs ( long long a , long long b , string num ) { if ( num == "" ) return true ; if ( a + b > 0 && num [ 0 ] == '0' ) return false ; for ( int i = 1 ; i < min (( int ) num . size () + 1 , 19 ); ++ i ) if ( a + b == stoll ( num . substr ( 0 , i ))) if ( dfs ( b , a + b , num . substr ( i , num . size () - i ))) return true ; return false ; } };

1class Solution : def isAdditiveNumber ( self , num : str ) -> bool : def dfs ( startIndex : int , out : List [ int ]) -> bool : # equal check is here if len ( out ) >= 3 and out [ - 1 ] != out [ - 2 ] + out [ - 3 ]: return False if startIndex == len ( num ): return len ( out ) >= 3 for i in range ( startIndex , len ( num )): current = num [ startIndex : i + 1 ] if ( len ( current ) > 1 and current [ 0 ] == '0' ): break out . append ( int ( current )) if dfs ( i + 1 , out ): return True out . pop () return False if not num : return False return dfs ( 0 , []) ############# # follow up: super large number, solve overflow issue class Solution : def addStrings ( num1 : str , num2 : str ) -> str : carry = 0 result = [] i , j = len ( num1 ) - 1 , len ( num2 ) - 1 while i >= 0 or j >= 0 or carry : x = int ( num1 [ i ]) if i >= 0 else 0 y = int ( num2 [ j ]) if j >= 0 else 0 sum = x + y + carry result . append ( str ( sum % 10 )) carry = sum // 10 i , j = i - 1 , j - 1 return '' . join ( reversed ( result )) def isAdditiveNumber ( num : str ) -> bool : n = len ( num ) for i in range ( 1 , n ): for j in range ( i + 1 , n ): num1 , num2 = num [: i ], num [ i : j ] if ( len ( num1 ) > 1 and num1 [ 0 ] == '0' ) or ( len ( num2 ) > 1 and num2 [ 0 ] == '0' ): continue while j < n : sum = addStrings ( num1 , num2 ) if not num . startswith ( sum , j ): break j += len ( sum ) num1 , num2 = num2 , sum if j == n : return True return False ############# class Solution : def isAdditiveNumber ( self , num : str ) -> bool : def dfs ( a , b , num ): if not num : return True if a + b > 0 and num [ 0 ] == '0' : return False for i in range ( 1 , len ( num ) + 1 ): if a + b == int ( num [: i ]): if dfs ( b , a + b , num [ i :]): return True return False n = len ( num ) for i in range ( 1 , n - 1 ): # 1st cut if i > 1 and num [ 0 ] == '0' : # 0 + 1 = 1 is fine, but 00 + 1 is wrong break for j in range ( i + 1 , n ): # 2nd cut, so making it a 3-segments if j - i > 1 and num [ i ] == '0' : break if dfs ( int ( num [: i ]), int ( num [ i : j ]), num [ j :]): # better than below, early stop return True return False

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem