Additive Numbers LeetCode (String with digits in additive sequence)

Additive number is a string whose digits can form 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.

For example:
"112358" is an additive number because 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

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

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

Solution:

1. To handle the overflow, we can use the next larger size primitives (or equivalent). I have used the Long for this and you can use your own choice.
2. The basic idea to solve this problem is to iterative throughout the digits from the beginning.
3. We use two loops and check if the numbers of the string pointed by this two loop indices can be found in the remaining portion of the string number.
4. Some test cases are also provided. If you want to modify the code, just add the new test case and make sure that the modified one passes all the test cases.
5. The runtime of the solution is O(n^2).

The problem is popular on LeetCode and other forums. A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Source code: Java