New update is available. Click here to update.

Last Updated: 24 Mar, 2021

Moderate

```
β1123β is a ninja string, since β1 + 1 = 2β and β1 + 2 = 3β.
```

```
Numbers in the ninja string cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
```

```
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.
```

```
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.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
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.

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

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.

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

- 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