Given a string str, 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 digits to make one additive sequence.
Examples:
Input: str = “235813”
Output: true
Explanation : One of the possible sequence is: 2 , 3 , 5 , 8 , 13
where 3 = 1 + 2 , 5 = 3 + 2 , 8 = 5 + 3 and 13 = 8 + 5 .Input: str = “199100199”
Output: true
Explanation : One of the possible sequence is : 1 , 99 , 100 , 199
where 100 = 99 + 1 , 199 = 100 + 99 gives the additive sequence.Input: str = “12345678”
Output: false
Explanation: No such sequence possible
Approach: The recursive approach is discussed in Set-1 of this article.
Backtracking Approach: The above problem can be solved using Backtracking in the following way.
- One of the basic requirements according to the problem statement is to check whether the given string follows the property of additive sequence i.e. every number in the sequence is the sum of the previous two numbers and this property holds true for all the numbers in the sequence.
- So there is no restriction on how to choose the first two numbers in the sequence ( as exactly two numbers are needed to check the additive sequence property ).
- So try all the possible ways to generate the first two numbers in the series and from the third number onwards have a comparison i.e. in order to hold the additive sequence property the next number in the series must be the sum of the previous two numbers.
- So if at any point of time the number generated so far is exceeding the sum of the previous two numbers, there no longer is a need to proceed further because this number will never be a part of an additive sequence. In that case backtrack and try for the rest of the combinations.
- If the number generated so far is the sum of the previous two numbers then recur for the remaining string using the previous two numbers as a reference and if reach the end of the string and the length of the additive sequence ( size of the vector ) is greater than or equal to 3 then the given string had an additive sequence.
- The moment additive sequence is found mark a global boolean variable as true ( to indicate that we had found a solution and to avoid checking of rest of the combinations ).
Below is the implementation of the above.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Variable to store the resultbool res;// Function to check the additive sequencevoid check_additive(string s, vector<long long>& v, long st){ // If the end is reached and vector // consists of more than 2 numbers then // one of the possible solution is found if (st == s.length() and v.size() > 2) { // Mark the res as true to indicate // the solution is found and // to avoid for trying // the rest of the combinations res = true; return; } long long a, b, c = 0; if (v.size() >= 2) { // Store the previous two numbers // of the sequence to check the // additive sequence property // for the next number b = v[v.size() - 1]; a = v[v.size() - 2]; } for (long i = st; i < s.length(); i++) { // Generate the number c = c * 10 + (s[i] - '0'); // Try all the possible ways // to generate the first two numbers // i.e. if vector consists of // less than two numbers and // no solution is found yet if (v.size() < 2 and !res) { v.push_back(c); check_additive(s, v, i + 1); // Pop the value to try for the // other combination v.pop_back(); } // If the number generated so far // is greater than the sum of // previous two numbers in // the sequence then it cannot be // a part of additive sequence // hence no need to proceed further else if (c > (a + b) and !res) return; // If the number generated so far // is equal to the sum of // previous two numbers then // it can be a part of additive // sequence; push it into vector // and check for remaining string else if (c == a + b and !res) { // Store it in the vector v.push_back(c); // Recur for remaining string check_additive(s, v, i + 1); // If unable to find solution // pop it and try for // other combination v.pop_back(); } } return;}// Function to check if additive sequencebool isAdditiveSequence(string str){ // In order to form additive sequence // the length of the string // must be atleast three if (str.length() <= 2) return false; vector<long long> v; res = false; check_additive(str, v, 0); return res;}// Driver codeint main(){ string str = "199100199"; bool ans = isAdditiveSequence(str); if (ans) cout << "true"; else cout << "false"; return 0;} |
Java
// Java code to implement the approachimport java.util.ArrayList;class GFG { // Variable to store the result static boolean res; // Function to check the additive sequence static void check_additive(String s, ArrayList<Integer> v, int st) { // If the end is reached and vector // consists of more than 2 numbers then // one of the possible solution is found if (st == s.length() && v.size() > 2) { // Mark the res as true to indicate // the solution is found and // to avoid for trying // the rest of the combinations res = true; return; } int a = 0, b = 0, c = 0; if (v.size() >= 2) { // Store the previous two numbers // of the sequence to check the // additive sequence property // for the next number b = v.get(v.size() - 1); a = v.get(v.size() - 2); } for (int i = st; i < s.length(); i++) { // Generate the number c = c * 10 + (s.charAt(i) - '0'); // Try all the possible ways // to generate the first two numbers // i.e. if vector consists of // less than two numbers and // no solution is found yet if (v.size() < 2 && !res) { v.add(c); check_additive(s, v, i + 1); // Pop the value to try for the // other combination v.remove(v.size() - 1); } // If the number generated so far // is greater than the sum of // previous two numbers in // the sequence then it cannot be // a part of additive sequence // hence no need to proceed further else if (c > (a + b) && !res) return; // If the number generated so far // is equal to the sum of // previous two numbers then // it can be a part of additive // sequence; push it into vector // and check for remaining String else if (c == a + b && !res) { // Store it in the vector v.add(c); // Recur for remaining String check_additive(s, v, i + 1); // If unable to find solution // pop it and try for // other combination v.remove(v.size() - 1); } } return; } // Function to check if additive sequence static boolean isAdditiveSequence(String str) { // In order to form additive sequence // the length of the String // must be atleast three if (str.length() <= 2) return false; ArrayList<Integer> v = new ArrayList<Integer>(); res = false; check_additive(str, v, 0); return res; } // Driver code public static void main(String args[]) { String str = "199100199"; boolean ans = isAdditiveSequence(str); if (ans) System.out.println("true"); else System.out.println("false"); }}// This code is contributed by saurabh_jaiswal. |
Python3
# python3 code to implement the approach# Variable to store the resultres = 0v = []# Function to check the additive sequencedef check_additive(s, st): global res global v # If the end is reached and vector # consists of more than 2 numbers then # one of the possible solution is found if (st == len(s) and len(v) > 2): # Mark the res as true to indicate # the solution is found and # to avoid for trying # the rest of the combinations res = True return a, b, c = 0, 0, 0 if (len(v) >= 2): # Store the previous two numbers # of the sequence to check the # additive sequence property # for the next number b = v[len(v) - 1] a = v[len(v) - 2] for i in range(st, len(s)): # Generate the number c = c * 10 + (ord(s[i]) - ord('0')) # Try all the possible ways # to generate the first two numbers # i.e. if vector consists of # less than two numbers and # no solution is found yet if (len(v) < 2 and (not res)): v.append(c) check_additive(s, i + 1) # Pop the value to try for the # other combination v.pop() # If the number generated so far # is greater than the sum of # previous two numbers in # the sequence then it cannot be # a part of additive sequence # hence no need to proceed further elif (c > (a + b) and not res): return # If the number generated so far # is equal to the sum of # previous two numbers then # it can be a part of additive # sequence; push it into vector # and check for remaining string elif (c == a + b and not res): # Store it in the vector v.append(c) # Recur for remaining string check_additive(s, i + 1) # If unable to find solution # pop it and try for # other combination v.pop() return# Function to check if additive sequencedef isAdditiveSequence(str): global res # In order to form additive sequence # the length of the string # must be atleast three if (len(str) <= 2): return False res = False check_additive(str, 0) return res# Driver codeif __name__ == "__main__": str = "199100199" ans = isAdditiveSequence(str) if (ans): print("true") else: print("false") # This code is contributed by rakeshsahni |
C#
// C# program of the above approachusing System;using System.Collections.Generic;class GFG{ // Variable to store the result static bool res; // Function to check the Additive sequence static void check_Additive(string s, List<int> v, int st) { // If the end is reached and vector // consists of more than 2 numbers then // one of the possible solution is found if (st == s.Length && v.Count > 2) { // Mark the res as true to indicate // the solution is found and // to avoid for trying // the rest of the combinations res = true; return; } int a = 0, b = 0, c = 0; if (v.Count >= 2) { // Store the previous two numbers // of the sequence to check the // Additive sequence property // for the next number b = v[v.Count - 1]; a = v[v.Count - 2]; } for (int i = st; i < s.Length; i++) { // Generate the number c = c * 10 + (s[i] - '0'); // Try all the possible ways // to generate the first two numbers // i.e. if vector consists of // less than two numbers and // no solution is found yet if (v.Count < 2 && !res) { v.Add(c); check_Additive(s, v, i + 1); // Pop the value to try for the // other combination v.Remove(v.Count - 1); } // If the number generated so far // is greater than the sum of // previous two numbers in // the sequence then it cannot be // a part of Additive sequence // hence no need to proceed further else if (c > (a + b) && !res) return; // If the number generated so far // is equal to the sum of // previous two numbers then // it can be a part of Additive // sequence; push it into vector // and check for remaining String else if (c == a + b && !res) { // Store it in the vector v.Add(c); // Recur for remaining String check_Additive(s, v, i + 1); // If unable to find solution // pop it and try for // other combination v.Remove(v.Count - 1); } } return; } // Function to check if Additive sequence static bool isAdditiveSequence(string str) { // In order to form Additive sequence // the length of the String // must be atleast three if (str.Length <= 2) return false; List<int> v = new List<int>(); res = true; check_Additive(str, v, 0); return res; } // Driver Code public static void Main() { string str = "199100199"; bool ans = isAdditiveSequence(str); if (ans) Console.Write("true"); else Console.Write("false"); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Variable to store the result let res; // Function to check the additive sequence function check_additive(s, v, st) { // If the end is reached and vector // consists of more than 2 numbers then // one of the possible solution is found if (st == s.length && v.length > 2) { // Mark the res as true to indicate // the solution is found and // to avoid for trying // the rest of the combinations res = true; return; } let a, b, c = 0; if (v.length >= 2) { // Store the previous two numbers // of the sequence to check the // additive sequence property // for the next number b = v[v.length - 1]; a = v[v.length - 2]; } for (let i = st; i < s.length; i++) { // Generate the number c = c * 10 + (s[i].charCodeAt(0) - '0'.charCodeAt(0)); // Try all the possible ways // to generate the first two numbers // i.e. if vector consists of // less than two numbers and // no solution is found yet if (v.length < 2 && res == false) { v.push(c); check_additive(s, v, i + 1); // Pop the value to try for the // other combination v.pop(); } // If the number generated so far // is greater than the sum of // previous two numbers in // the sequence then it cannot be // a part of additive sequence // hence no need to proceed further else if (c > (a + b) && res == false) return; // If the number generated so far // is equal to the sum of // previous two numbers then // it can be a part of additive // sequence; push it into vector // and check for remaining string else if (c == a + b && res == false) { // Store it in the vector v.push(c); // Recur for remaining string check_additive(s, v, i + 1); // If unable to find solution // pop it and try for // other combination v.pop(); } } return; } // Function to check if additive sequence function isAdditiveSequence(str) { // In order to form additive sequence // the length of the string // must be atleast three if (str.length <= 2) return false; let v = []; res = false; check_additive(str, v, 0); return res; } // Driver code let str = "199100199"; let ans = isAdditiveSequence(str); if (ans) document.write("true"); else document.write("false"); // This code is contributed by Potta Lokesh </script> |
Output
true
Time Complexity: O(N*N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
