Last Updated: 24 Mar, 2021
Additive Number
Moderate
Asked in companies
Ninja developed his own coding platform and he wants all the questions of string to be uploaded on his platform. So he wants to create test cases of the string but as usual, he uses his own ninja technique for selecting the strings and calls such strings as ninja strings. A valid ninja string must contain at least three numbers and except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
So help our ninja to write the code so he is able to check whether the string is a ninja string or not.
So your task is to write a code for a given string containing only digits ‘0 - 9’ for determining whether the string is a ninja string or not.
Example :
‘1123’ is a ninja string, since ‘1 + 1 = 2’ and ‘1 + 2 = 3’.
Note :
Numbers in the ninja string cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Input Format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains a string ‘S’, representing the string for which you have to determine if this string is a ninja string or not.
Output Format :
For each test case, print a single line as ‘True’ or ‘False’ as per the given condition.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= |S| <= 30
Where ‘T’ represents the number of test cases and ‘S’ represents the given string.
Time Limit: 1 second
Approaches
The idea is here to recursively call the function of string for each length.
Algorithm:
- We will declare a helper function which checks whether the sum is equal to the previous two elements.
- Now we check that the sum of the first and second numbers is exactly equal to the rest of the string.
- If yes then we directly return the result as ‘True’
- Else check that sum string is the prefix of the rest of the string or not
- If yes then we call recursively with the second number and rest of the string after removing the second number from the rest of the string and if the string is not a prefix of the rest of the string then we return ‘False’.
- Thus in this way, we arrive at our final answer.
Description of ‘helper’ function
This function is used to check whether the the sum of first two previous numbers is equal to the element of the string or not.
This function will take three-parameter:
- Str: a string up to we want
- Str1: first previous value
- Str2: second previous value.
bool isHelper(String str, string str1, string str2):
- It first checks if the sum of str1 + str 2 by converting it in numerical form is equal or not.
- If it is equal then return true
- Else :
- if sum size is greater than str, then no possible sequence further OR if str is not a prefix of sum string, then no possible sequence further
- next recursive call will have str2 as the first number, a sum as the second number, and string str as the third number after removing prefix sum string from str
The idea here is to iterate through the string and check whether the number is the sum of the previous two numbers.
Algorithm:
- So we start with adding a number from the first index and second index and check whether the sum is equal to the next string elements.
- The sum can be equal to one, two, or the rest of the elements of strings so we have to check each and every possibility.
- If it is equal we subtract the first element from this and move further if it comes out wrong we simply return ‘False’.
- In this way, we traverse our whole string and if we are able to traverse the whole string we will return ‘True as it shows we have founded a valid additive number