New update is available. Click here to update.
Last Updated: 24 Mar, 2021
##### Additive Number
Moderate
Problem statement

#### 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

## 01Approach

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