String with additive sequence

Given a string, the task is to find whether it contains an additive sequence or not. A string contains an additive sequence if its digits can make a sequence of numbers in which every number is addition of previous two numbers. A valid string should contain at least three digit to make one additive sequence.

Examples:

Input : s = “235813”
Output : true
2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13

Input : s = “199100199”
Output : true
1 + 99 = 100, 99 + 100 = 199

Input : s = “12345678”
Output : false

This problem can be solved recursively, note that number of digits in added value can’t be smaller than digits in any of its operand that is why we will loop till (length of string)/2 for first number and (length of string – first number’s length)/ 2 for second number to ignore invalid result.
Next thing to note is, first and second number can’t start with 0, which is checked in below code by isValid method. When we call recursively, we check that sum of first and second number is exactly equal to rest of string. If yes then direct return the result else check that sum string is prefix of rest of string or not, If yes then call recursively with second number, sum string and rest of string after removing sum string from rest of string and if sum string is not prefix of rest of string then no solution in available.

Below is C++ implementation.

// C++ program to check whether a string
// makes an additive sequence or not
#include <bits/stdc++.h>
using namespace std;
// Checks whether num is valid or not, by
// checking first character and size
bool isValid(string num)
{
    if (num.size() > 1 && num[0] == '0')
        return false;
    return true;
}
// returns int value at pos string, if pos is
// out of bound then returns 0
int val(string a, int pos)
{
    if (pos >= a.length())
        return 0;
    //  converting character to integer
    return (a[pos] - '0');
}
// add two number in string form and return
// result as a string
string addString(string a, string b)
{
    string sum = "";
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;
    //  loop untill both string get processed
    while (i >= 0 || j >= 0)
    {
        int t = val(a, i) + val(b, 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 checkAddition(list<string>& res, string a,
                             string b, string c)
{
    //  both first and second number should be valid
    if (!isValid(a) || !isValid(b))
        return false;
    string sum = addString(a, b);
    //  if sum is same as c then direct return
    if (sum == c)
    {
        res.push_back(sum);
        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 (c.size() <= sum.size() ||
        sum != c.substr(0, sum.size()))
        return false;
    else
    {
        res.push_back(sum);
        
        //  next recursive call will have b as first
        //  number, sum as second number and string
        //  c as third number after removing prefix
        //  sum string from c
        return checkAddition(res, b, sum,
                             c.substr(sum.size()));
    }
}
//  Method returns additive sequence from string as
// a list
list<string> additiveSequence(string num)
{
    list<string> res;
    int l = num.length();
    // loop untill l/2 only, because if first
    // number is larger,then no possible sequence
    // later
    for (int i = 1; i <= l/2; i++)
    {
        for (int j = 1; j <= (l - i)/2; j++)
        {
            if (checkAddition(res, num.substr(0, i),
                              num.substr(i, j),
                              num.substr(i + j)))
            {
                // adding first and second number at
                // front of result list
                res.push_front(num.substr(i, j));
                res.push_front(num.substr(0, i));
                return res;
            }
        }
    }
    // If code execution reaches here, then string
    // doesn't have any additive sequence
    res.clear();
    return res;
}
//  Method to print result list
void printResult(list<string> res)
{
    for (auto it = res.begin(); it != res.end(); it++)
        cout << *it << " ";
    cout << endl;
}
//  Driver code to test above methods
int main()
{
    string num = "235813";
    list<string> res = additiveSequence(num);
    printResult(res);
    num = "199100199";
    res = additiveSequence(num);
    printResult(res);
    return 0;
}

Output:

2 3 5 8 13 
1 99 100 199 

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/string-with-additive-sequence/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar