Additive Number

Additive Number

What is this problem about?

An Additive Number is a string where the digits form an additive sequence. In such a sequence, every number (starting from the third) is the sum of the preceding two. For example, "112358" is additive because $1+1=2, 1+2=3, 2+3=5, \text{ and } 3+5=8$. The Additive Number coding problem asks you to determine if a given string is additive.

Why is this asked in interviews?

Companies like Meta and Google ask this to test your Backtracking and String parsing skills. Unlike some problems with fixed-length numbers, the numbers in an additive sequence can have any number of digits. You must explore various ways to split the string, which requires a recursive or iterative search strategy.

Algorithmic pattern used

This is a classic Backtracking interview pattern. You pick the first two numbers (there are $O(N^2)$ ways to do this), and then the rest of the sequence is strictly determined by those two. You recursively check if the next part of the string matches the sum of the previous two numbers.

Example explanation

Input: "199100199"

1. Try first number "1", second number "99".
2. Sum is $1 + 99 = 100$. The string starts with "100" after "99". This works!
3. Now the "previous two" are "99" and "100".
4. Sum is $99 + 100 = 199$. The string has "199" remaining.
5. All characters used. Return true.

Common mistakes candidates make

• Leading Zeros: The problem usually states that numbers cannot have leading zeros unless the number is just "0". Candidates often forget to validate "05" as invalid.
• Integer Overflow: Additive numbers can be very long (e.g., 50 digits). Using a standard long or int to store the sum will fail. You must use string-based addition or BigInteger.
• Incomplete Search: Only trying to split the string into single digits and failing to realize that numbers like "199" are possible.

Interview preparation tip

Since the first two numbers determine the entire sequence, you don't need full backtracking for the whole string. Once you've picked the first two, the rest is a simple iterative check. This reduces the search space significantly.