Additive Number

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
27 upvotes
Asked in companies
AmazonalibabaVFISLK Global Services

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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
Sample Input 1 :
2
112358
2356
Sample Output 1 :
True
False
Explanation Of Sample Input 1 :
Test Case 1:
In the first line, there is the number of test cases i.e., ‘2’, and in the next line ‘112358’ is the given string so now we look for our condition 
‘1 + 1 = 2’
‘1 + 2 = 3’
‘2 + 3 = 5’
‘3 + 5 = 8’
Hence we return ‘True’ as it satisfies the given condition for the ninja string.

Test Case 2:
For this test case given string is ‘2356’ 
‘2 + 3 = 5’
But ‘3 + 5 = 8’ but in string ‘6’ is present so we return ‘False’ as it doesn’t satisfy the given condition for the ninja string.
Sample Input 2 :
2
235813
131528
Sample Output 2 :
True
True
Explanation Of Sample Input 2 :
Test Case 1:
In the first line, there is the number of test cases i.e., ‘1’, and in the next line ‘235813’ is the given string so now we look for our condition 
‘2 + 3 = 5’
‘3 + 5 = 8’
‘5 + 8 = 13’
Hence we return ‘True’ as it satisfies the given condition for the ninja string.


Test Case 2:
'131528’ is the given string so now we look for our condition 
13 + 15 = 28
Hence we return ‘True’ as it satisfies the given condition for the ninja string.
Hint

Can you think of a recursive approach?

Approaches (2)
Recursive Approach

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
Time Complexity

O(N ^ 2), where ‘N’ is the length of the input string.

 

As we are running a loop from ‘i’ till N / 2, and another nested list inside this loop that takes O(N) time. Hence the final time complexity will be O(N ^ 2).

Space Complexity

O(N), where ‘N’ is the length of the input string.

 

As recursion uses a stack of size ‘N’.

Code Solution
(100% EXP penalty)
Additive Number
Full screen
Console