[Solved] Additive Number Contest Problem

Additive Number: 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.

Additive Number Contest Problem

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 :

1
235813

Sample Output 2 :

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.

Solution

Recursive Approach

The idea is here to recursively call the function of the string for each length.

Algorithm:

• We will declare a helper function that 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 the sum string is the prefix of the rest of the string or not
    • If yes then we call recursively with the second number and the 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 the 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, another nested list inside this loop 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’.

/*
    Time complexity: O(N ^ 2)
    Space complexity: O(N)

    Where N represents the size of the given string.
*/

public class Solution 
{
    public static boolean isValid(String str)
    {
        if (str.length() > 1 && str.charAt(0) == '0')
        {
            return false;
        }
    
        return true;
    }
    
    /*
        Returns int value at pos string, if pos is
        out of bound then returns 0
    */
    public static int val(String str1, int pos)
    {
        if (pos < 0 || pos >= str1.length())
        {
            return 0;
        }
    
        //  Converting character to integer
        int position = (str1.charAt(pos) - '0');

        return position;
    }
    
    /*
        Add two number in string form and return
        result as a string
    */
    public static String addString(String str1, String str2)
    {
        String sum = "";
        int i = str1.length() - 1;
        int j = str2.length() - 1;
        int carry = 0;
    
        //  Loop untill both string get processed
        while (i >= 0 || j >= 0)
        {
            int t = val(str1, i) + val(str2, j) + carry;
            sum += String.valueOf(t % 10);
            carry = t / 10;
            i--;
            j--;
        }
    
        if (carry > 0)
        {
            sum += String.valueOf(carry);
        }
        
        StringBuilder sum1 = new StringBuilder(sum);
        sum1.reverse();
        return sum1.toString();
    }
    
    //  Recursive method to check c = a + b
    public static boolean isHelper(String str1, String str2, String str)
    {
        //  Both first and second number should be valid
        if (isValid(str1) == false || isValid(str2) == false)
        {
            return false;
        }
    
        String sum = addString(str1, str2);
    
        //  If sum is same as c then direct return
        if (sum.compareTo(str) == 0)
        {
            return true;
        }
    
        /*
            If sum size is greater than c, then no
            possible sequence further OR if c is not
            prefix of sum string, then no possible
            sequence further
        */
        if (str.length() <= sum.length() || sum.compareTo(str.substring(0, sum.length())) != 0)
        {
            return false;
        }
        else
        {
    
            /*
                Next recursive call will have str2 as first
                number, sum as second number and string
                str as third number after removing prefix
                sum string from str
            */
            return isHelper(str2, sum, str.substring(sum.length()));
        }
    }

	public static boolean ninjaString(String str) 
    {
        int l = str.length();

        /*
            Loop until l/2 only, because if first
            number is larger,then no possible sequence exist
        */
        for (int i = 1; i <= l / 2; i++)
        {
            for (int j = 1; j <= (l - i) / 2; j++)
            {
                if (isHelper(str.substring(0, i), str.substring(i, i + j), str.substring(i + j)) == true)
                {
                    return true;
                }
            }
        }
    
        /*
             If code execution reaches here, then string
             doesn't have any additive sequence
        */
        return false;
	}
}

/*
    Time complexity: O(N ^ 2)
    Space complexity: O(N)

    Where N represents the size of the given string.
*/

#include <algorithm>

bool isValid(string &str)
{
    if (str.size() > 1 && str[0] == '0')
    {
        return false;
    }

    return true;
}

/*
    Returns int value at pos string, if pos is
    out of bound then returns 0
*/
int val(string &str1, int pos)
{
    if (pos >= str1.length())
    {
        return 0;
    }

    //  Converting character to integer
    int position = (str1[pos] - '0');

    return position;
}

/*
    Add two number in string form and return
    result as a string
*/
string addString(string &str1, string &str2)
{
    string sum = "";
    int i = str1.length() - 1;
    int j = str2.length() - 1;
    int carry = 0;

    //  Loop untill both string get processed
    while (i >= 0 || j >= 0)
    {
        int t = val(str1, i) + val(str2, j) + carry;
        sum += (t % 10 + '0');
        carry = t / 10;
        i--;
        j--;
    }

    if (carry)
    {
        sum += (carry + '0');
    }

    reverse(sum.begin(), sum.end());

    return sum;
}

//  Recursive method to check c = a + b
bool isHelper(string str1, string str2, string str)
{
    //  Both first and second number should be valid
    if (isValid(str1) == false or isValid(str2) == false)
    {
        return false;
    }

    string sum = addString(str1, str2);

    //  If sum is same as c then direct return
    if (sum == str)
    {
        return true;
    }

    /*
        If sum size is greater than c, then no
        possible sequence further OR if c is not
        prefix of sum string, then no possible
        sequence further
    */
    if (str.size() <= sum.size() or sum != str.substr(0, sum.size()))
    {

        return false;
    }
    else
    {

        /*
            Next recursive call will have str2 as first
            number, sum as second number and string
            str as third number after removing prefix
            sum string from str
        */
        return isHelper(str2, sum, str.substr(sum.size()));
    }
}

bool ninjaString(string &str)
{
    int l = str.length();

    /*
        Loop until l/2 only, because if first
        number is larger,then no possible sequence exist
    */
    for (int i = 1; i <= l / 2; i++)
    {
        for (int j = 1; j <= (l - i) / 2; j++)
        {
            if (isHelper(str.substr(0, i), str.substr(i, j), str.substr(i + j)) == true)
            {
                return true;
            }
        }
    }

    /*
         If code execution reaches here, then string
         doesn't have any additive sequence
    */
    return false;
}

'''
    Time complexity: O(N ^ 2)
    Space complexity: O(N)

    Where N represents the size of the given string.
'''

def isValid(s):

    if len(s) > 1 and s[0] == '0':
        return False

    return True


def addString(str1, str2):

    ans = int(str1) + int(str2)
    curSum = str(ans)

    return curSum

#  Recursive method to check c = a + b


def isHelper(str1, str2, s):

    #  Both first and second number should be valid
    if (isValid(str1) == False or isValid(str2) == False):
        return False

    curSum = addString(str1, str2)
    #  If curSum is same as c then direct return
    if (curSum == s):

        return True

    '''
        If curSum size is greater than c, then no
        possible sequence further OR if c is not
        prefix of curSum string, then no possible
        sequence further
    '''
    if (len(s) <= len(curSum) or curSum != s[0:len(curSum)]):
        return False

    else:

        '''
            Next recursive call will have str2 as first
            number, curSum as second number and string
            s as third number after removing prefix
            curSum string from s
        '''
        return isHelper(str2, curSum, s[len(curSum):len(s)])


def ninjaString(s):

    l = len(s)

    '''
        Loop until l/2 only, because if first
        number is larger,then no possible sequence exist
    '''
    for i in range(1, (l//2)+1):
        for j in range(1, ((l-i)//2)+1):
            if isHelper(s[0:i], s[i:i + j], s[i + j:len(s)]) == True:
                return True

    '''
         If code execution reaches here, then string
         doesn't have any additive sequence
    '''
    return False

Iterative Approach

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

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(1).

No extra space is being used.

/*
    Time complexity: O(N ^ 2)
    Space complexity: O(1)

    Where N represents the size of the given string.
*/

public class Solution 
{
    public static boolean startsWith(String str, String str1, int r)
    {
        int k = 0;
        int l = str1.length();
    
        // Loop upto length of str1
        while (l > 0)
        {
            if (str.charAt(r) != str1.charAt(k))
            {
                return false;
            }
            r += 1;
            k += 1;
            l--;
        }
    
        return true;
    }
    
    public static boolean isValid(int i, int j, String str)
    {
        if (str.charAt(0) == '0' && i > 1)
        {
            return false;
        }
    
        if (str.charAt(i) == '0' && j > 1)
        {
            return false;
        }
    
        String str1 = str.substring(0, i);
        long x1 = Long.parseLong(str1);
    
        String str2 = str.substring(i, i + j);
        long x2 = Long.parseLong(str2);
    
        String sum = "";
    
        for (int start = i + j; start != str.length(); start += sum.length())
        {
            x2 = x2 + x1;
            x1 = x2 - x1;
    
            sum = String.valueOf(x2);
    
            // Call function to check whether string is equal or not
            if (startsWith(str, sum, start) == false)
            {
                return false;
            }
        }
    
        return true;
    }
    
    public static boolean ninjaString(String str) 
    {
        int n = str.length();

        /*
            Loop until n/2 only, because if first
            number is larger,then no possible sequence exists
        */
        for (int i = 1; i <= n / 2; ++i)
        {
            for (int j = 1; Math.max(j, i) <= n - i - j; ++j)
            {
                if (isValid(i, j, str) == true)
                {
                    return true;
                }
            }
        }
    
        return false;
    }
}

/*
    Time complexity: O(N ^ 2)
    Space complexity: O(1)

    Where N represents the size of the given string.
*/

#include <algorithm>

bool startsWith(string &str, string &str1, int r)
{
    int k = 0;
    int l = str1.length();

    // Loop upto length of str1
    while (l--)
    {
        if (str[r] != str1[k])
        {
            return false;
        }
        r += 1;
        k += 1;
    }

    return true;
}

bool isValid(int i, int j, string &str)
{
    if (str[0] == '0' and i > 1)
    {
        return false;
    }

    if (str[i] == '0' and j > 1)
    {
        return false;
    }

    string str1 = str.substr(0, i);
    long long x1 = stoll(str1);

    string str2 = str.substr(i, j);
    long long x2 = stoll(str2);

    string sum;

    for (int start = i + j; start != str.length(); start += sum.length())
    {
        x2 = x2 + x1;
        x1 = x2 - x1;

        sum = to_string(x2);

        // Call function to check whether string is equal or not
        if (startsWith(str, sum, start) == false)
        {
            return false;
        }
    }

    return true;
}

bool ninjaString(string &str)
{
    int n = str.length();

    /*
        Loop until n/2 only, because if first
        number is larger,then no possible sequence exists
    */
    for (int i = 1; i <= n / 2; ++i)
    {
        for (int j = 1; max(j, i) <= n - i - j; ++j)
        {
            if (isValid(i, j, str) == true)
            {
                return true;
            }
        }
    }

    return false;
}

'''
    Time complexity: O(N ^ 2)
    Space complexity: O(1)

    Where N represents the size of the given string.
'''

def startsWith(s, str1, r):
    k = 0
    l = len(str1)

    # Loop upto length of str1
    while l > 0:
        l -= 1
        if (s[r] != str1[k]):
            return False

        r += 1
        k += 1

    return True


def isValid(i, j, s):

    if (s[0] == '0' and i > 1):
        return False

    if (s[i] == '0' and j > 1):
        return False

    str1 = s[0:i]
    x1 = int(str1)

    str2 = s[i:i+j]
    x2 = int(str2)

    curSum = ""

    start = i + j
    while start != len(s):
        x2 = x2 + x1
        x1 = x2 - x1

        curSum = str(x2)

        # Call function to check whether string is equal or not
        if (startsWith(s, curSum, start) == False):
            return False

        start += len(curSum)

    return True


def ninjaString(s):

    n = len(s)

    '''
        Loop until n/2 only, because if first
        number is larger,then no possible sequence exists
    '''
    for i in range(1, (n//2)+1):
        j = 1
        while max(j, i) <= n - i - j:
            if (isValid(i, j, s) == True):
                return True

            j += 1

    return False

Java shortcode

public class Solution {
    public static boolean ninjaString(String str) {
		int prePreVal = str.charAt(0)- '0';
		int preVal = str.charAt(1) - '0';
		return isNinjaString(2, prePreVal, preVal, str);
	}
    
    public static boolean isNinjaString(int idx, int prePreVal, int preVal, String str) {
    
		if (idx == str.length()) {
			return true;
		}

		int preSum = prePreVal + preVal;
		int preSumLen = String.valueOf(preSum).length();
		
		if ((idx + preSumLen) <= str.length()) {
            int currSum = Integer.parseInt(str.substring(idx, idx + preSumLen));
            if(preSum == currSum){
			return isNinjaString(idx + preSumLen, preVal, preSum, str);
            }
		}
		return false;
    }
}

Happy Learning – If you require any further information, feel free to contact me.