Problem: 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.
Given a string containing only digits, write a method to check if input string is an additive number. Please note that numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Example:
Input: "1235813" Output: true Explanation: The digits can form an additive sequence: 1, 2, 3, 5, 8, 13. 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13
Approach: The problem can be solved using recursion. Basically what we want to do is choose the starting two numbers which can form additive sequence so we we will choose 2 starting number say num1 and num2 as 1 by 1 of every length possible and see if selecting them as starting numbers are forming additive sequence.
In the method we will see if sum of num1 and num2 is a prefix of rest of the string. If yes, then we can call the method recursively by taking first number as num2 and second number as sum of num1 and num2 and rest of the string as third argument(excluding sum).
If anywhere we find that current sum is not a prefix of remaining string then we return false. We continue to call the method recursively till we reach to the end that means remaining string become empty.
At any point we find a solution we return true. We can be smart about choosing the numbers as length of sum of two numbers can't be less than any of the operand's (number) length so we can loop till (length of string)/2 for first number and (length of string – first number’s length)/ 2 for second number to ignore invalid result.
Implementation in C#:
public static bool IsAdditiveNumber(string num)
{
if (num?.Length < 3)
{
return false;
}
int length = num.Length;
for (int i = 1; i <= length / 2; ++i)
{
for (int j = 1; j <= (length - i) / 2; ++j)
{
if (IsAdditiveSequence(num.Substring(0, i), num.Substring(i, j), num.Substring(i + j)))
{
return true;
}
}
}
return false;
}
private static bool IsAdditiveSequence(string str1, string str2, string remainingString)
{
if (!IsValid(str1) || !IsValid(str2))
{
return false;
}
if (remainingString == string.Empty)
{
return true;
}
long num1 = long.Parse(str1);
long num2 = long.Parse(str2);
string currSum = (num1 + num2).ToString();
if (remainingString.Length < currSum.Length || remainingString.Substring(0, currSum.Length) != currSum)
{
return false;
}
return IsAdditiveSequence(str2, currSum, remainingString.Substring(currSum.Length));
}
private static bool IsValid(string str)
{
if(str.Length > 1 && str[0] == '0')
{
return false;
}
return true;
}
Complexity: O(n^3)
