Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Approach
3.1.
Java
3.2.
C++
3.3.
Python
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is FIFO in Programming?
4.2.
What type of Data Structure is a string?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Additive Number

Author Saksham Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
DSA Problems

Introduction

Maths is a very fun subject to study, and so is recursion in programming, but what happens when these two are combined together? Today, we will discuss one such problem, i.e., additive number, where your concepts related to recursion and maths would be judged.

An additive number is a string of numbers that can be used to create an additive sequence. Also, at least three numbers must be present in a valid additive sequence with the exception of the first two numbers, and each subsequent number in the sequence must be the sum of the preceding two.

Understanding the Problem

The problem is fairly simple to understand. We will be given a string, and we have to check whether it’s an additive number or not. Now an additive number is a string of numbers that can be used to create an additive sequence.

Also, at least three numbers must be present in a valid additive sequence with the exception of the first two numbers. And each subsequent number in the sequence must be the sum of the preceding two.

Let’s see some examples to understand better.

Number = "112358"

The output would be true as the digits can form an additive sequence: 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Approach

The trick here is to choose only the first two numbers.

What two numbers?

Let’s understand this better by an example. Let’s say the given number, ‘N’ is 12315. In order to check ‘N’ is an additive number we choose the first number, let’s say ‘A’ as 12, and the second number, let’s say ‘B’ as 3. Now we can see that ‘A’ + ‘B’ = 12 + 3 = 15.

Once we choose these two numbers, later can be handled by recursion. But how are we going to choose the first two numbers? We will try all possible combinations and will come to a conclusion.

Let the first number be ‘A’, the second number be ‘B’, and the length of the string be ‘L’ then:

  1. For the first number ‘A’, it can be a minimum of 1 digit and can go up to ‘i’ digits where i <= (L - 1) / 2 because the third digit of the number should be at least as long as the first number.
  2. For the second number, ‘B’, it can be a minimum of 1 digit and can go up to ‘j’ digits, excluding the first number. The limit for ‘j’ is a little bit tricky because we don't know whether A or B is longer. The remaining string (with length L - j) after excluding ‘A’ and ‘B’ should have a length of at least max(length A, length B), where the length of A = i and length of B = j - i, thus L - j  >=  max( j - i, i).

This might be a little overwhelming for you but bear with me for a few more minutes and you will get the intuition perfectly.

But now, what’s next?

We will create a helper function isAdditive() which will take one string and two integers as its parameters and will check if these three are additive or not. Thus after selecting ‘A’ and ‘B’, we will call this function with the remaining string, and if it returns true, we will return true else, we will continue to the next choice of ‘B’ and ‘A’ until there is no more choice for ‘B’ or ‘A’. if we are left with no more choice for ‘B’ and ‘A’, we will return false.

But how is this isAdditive() going to be implemented?

This function will take three parameters ‘STR’, ‘NUM1’, ‘NUM2’. Base case would be very simple if it’s an empty string, then we will return true as we have reached the end of the string.

Then we will find out the sum of ‘NUM1’ and ‘NUM2’ representing ‘A’ and ‘B’ numerical values, respectively. If the sum(string form) is not a prefix of ‘STR’, then return false as it has to be an additive number as mentioned in the question. Else we will call this recursive function for the remaining string(string left after ‘SUM’ has been removed as its prefix ), ‘NUM2’, and integer value of ‘SUM’.

Below is the code for the above explanation

Java

import java.util.*;
import java.lang.*;
import java.io.*;

class AdditiveNumber
{
public boolean isAdditive(String str, long num1, long num2)
    {
        // If we reach the end of the string, return true.
        if (str.equals(""))
            return true;

        long sum = num1 + num2;
        String s = ((Long)sum).toString();

        // If the string does not start with sum of num1 and num2,  
          returns false.
        if (!str.startsWith(s))
            return false; 

        // Recursively checks for the remaining string.
        return isAdditive(str.substring(s.length()), num2, sum);
    }
public boolean isAdditiveNumber(String num)
    {
        int L = num.length();

        // Loop to choose the first number 'A'.
        for (int i = 1; i <= (L - 1) / 2; i++)
        {
            // 'A' cannot start with a 0 if its length is more
                Than 1.
            if (num.charAt(0) == '0' && i >= 2)
                break; 

            // Loop to choose the second number 'B'.
            for (int j = i + 1; L - j >= j - i && L - j >= i; j++)
            {
                // 'B' cannot start with a 0 if its length is more than 1.
                if (num.charAt(i) == '0' && j - i >= 2)
                    break;

                long num1 = Long.parseLong(num.substring(0, i)); 
                long num2 = Long.parseLong(num.substring(i, j)); 
              
                // Remaining String.
                String substr = num.substring(j);                
                // Return true if isAdditive returns true.
                if (isAdditive(substr, num1, num2))
                    return true;                           }
        }

        // No more combination possible, return false.
        return false;    
}

public static void main(String[] args)
    {
        AdditiveNumber ad = new AdditiveNumber();
        Scanner myObj = new Scanner(System.in); 

        // Taking input.
        String s1 = myObj.nextLine();
        System.out.println(ad.isAdditiveNumber(s1));
    }
}
You can also try this code with Online C++ Compiler
Run Code

 

C++

#include<bits/stdc++.h>
using namespace std;
string sum(string s1,string s2){
   reverse(s1.begin(),s1.end());
   reverse(s2.begin(),s2.end());
   string res; int c=0; int i=0;
   for(; i<min(s1.length(),s2.length()); i++)
   {
       int n=(s1[i]-'0'+s2[i]-'0')+c;
       res+=to_string(n%10);
       c=n/10;
   }
   for(; i<s1.length(); i++)
   {
       int n=(s1[i]-'0')+c;
       res+=to_string(n%10);
       c=n/10;
   }
   for(; i<s2.length(); i++)
   {
       int n=(s2[i]-'0')+c;
       res+=to_string(n%10);
       c=n/10;
   }
   while(c!=0){
       res+=to_string(c%10);
       c=c/10;
   }
   reverse(res.begin(),res.end());
   return res;
}
//backtracking function
bool check(string s1,string s2,string s)
{
   if(s=="") return true;
   string n=sum(s1,s2);
   if(n==s.substr(0,n.length()) && check(s2,n,s.substr(n.length()))){
       return true;
   }
   else{
       return false;
   }
}
bool isAdditiveNumber(string num) {
   string s1,s2;
   for(int i=1; i<num.length(); i++){
       for(int j=i+1; j<num.length(); j++){
 //creating first two numbers
           s1=num.substr(0,i);
           s2=num.substr(i,j-i);
  //checking that the number contains leading 0's or not
           if(s2[0]=='0' && s2.length()>1) continue;
           string s=num.substr(j);
           if(check(s1,s2,s)) return true;
       }
   }
   return false;
}
int main()
{
   string num;
   cin>>num;
  bool ans=isAdditiveNumber(num);
  ans=ans?true:false;
  cout<< boolalpha <<ans;
}
You can also try this code with Online C++ Compiler
Run Code

 

Python

def isAdditiveNumber(num):
   def add(prev,curr,index):
       if index==len(num):
           return 1
       total=str(int(prev)+int(curr))
       if total==num[index:index+len(total)]:
           return add(curr,total,index+len(total))
       else:
           return False
   for i in range(len(num)):
       if num[0]=='0' and i>0:
           break
       for j in range(i+1,len(num)):
           prev=num[0:i+1]
           curr=num[i+1:j+1]
           if curr[0]=='0' and len(curr)>1:
               break
           total=str(int(prev)+int(curr))
           if total==num[j+1:j+1+len(total)]:
               if  add(curr,total,j+1+len(total)):
                   return True
   return False
num=input()
print(isAdditiveNumber(num))
You can also try this code with Online Python Compiler
Run Code

Input

112358
1234

Output

true
false

Complexity Analysis

Time Complexity

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

As we are using two nested for loops and each loop costs us O(N) time thus the overall time complexity is O(N ^ 2).

Space Complexity

The Space Complexity is O(N), where ‘N’ is the length of the string.

As we are creating a recursive function which in the worst case would be called ‘N’ times so the space used by the recursion stack would be O(N).

Also check out - Substr C++

Must Read Recursion in Data Structure

Frequently Asked Questions

What is FIFO in Programming?

FIFO stands for First in First Out. It means that the element first inserted into the data structure is the first one to be processed. Example Queue

What type of Data Structure is a string?

A string is a Linear Data Structure.

Conclusion

We saw how we solved the additive number problem using recursion. You must be thrilled about learning a new concept but the road to becoming a recursion champ is still very long. So head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass