Posted on by Kalkicode
Code Backtracking

Split a numeric string into fibonacci sequence

The given problem is about splitting a given numeric string into a Fibonacci sequence. In this context, a Fibonacci sequence is a series of numbers where each number (after the first two) is the sum of the two preceding ones. The goal is to determine if the given numeric string can be split into a sequence of Fibonacci numbers. If such a split is possible, the program should output the sequence; otherwise, it should indicate that no such split exists.

Problem Statement

Given a numeric string, we need to determine if it can be split into a sequence of Fibonacci numbers. If possible, we need to output the sequence; otherwise, indicate that no such split exists.

Example

Let's take an example to illustrate the problem. Consider the numeric string "121131427". The program should check if it can be split into a sequence of Fibonacci numbers. The output should be a sequence that satisfies the Fibonacci property. In this case, the output should be: "12 1 13 14 27".

Idea to Solve

To solve this problem, we can use a recursive approach combined with backtracking. The idea is to start with the first two numbers in the sequence and then iteratively try to extend the sequence by adding subsequent numbers to it. At each step, we check if the current subsequence forms a valid Fibonacci sequence.

Pseudocode

function splitFibonacci(pos, number, fib):
    if pos == length of number and size of fib >= 3:
        return true
    
    num = 0
    stop = false
    
    for i from pos to length of number:
        num = num * 10 + (number[i] - '0')
        
        if num > MAX_INT or (number[pos] == '0' and i > pos):
            stop = true
        
        else if size of fib > 2 and num > fib[last] + fib[last-1]:
            stop = true
        
        else if size of fib < 2 or num == fib[last] + fib[last-1]:
            fib.add(num)
            if splitFibonacci(i + 1, number, fib):
                return true
            fib.remove(last)
    
    return false

function fibonacciSeries(number):
    fib = empty ArrayList
    if splitFibonacci(0, number, fib):
        return fib
    else:
        return "None"

Algorithm Explanation

  1. The splitFibonacci function takes the current position pos in the numeric string, the string number itself, and an ArrayList fib to store the Fibonacci sequence.
  2. If the position is at the end of the string and the size of the Fibonacci sequence is at least 3, return true to indicate a valid sequence.
  3. Initialize num as 0 and stop as false.
  4. Loop through the string from the current position to the end.
  5. Append digits to num and check for conditions that would stop the loop: if num exceeds the maximum integer value or if a leading zero is encountered.
  6. Check if the current subsequence does not follow the Fibonacci property or if it matches the next Fibonacci number in the sequence.
  7. If it matches, add the number to the Fibonacci sequence, call splitFibonacci recursively for the next position, and if it returns true, the current sequence is part of the Fibonacci split. Otherwise, remove the last added number and continue checking.
  8. If no valid sequence is found, return false.
  9. The fibonacciSeries function initializes the fib ArrayList and calls splitFibonacci. If a valid sequence is found, it returns the sequence; otherwise, it returns "None".

Code Solution

// Java program for
// Split a numeric string into fibonacci sequence
import java.util.ArrayList;
public class FibonacciSeries
{
    // Find fibonacci sequence in given number when if it is exist
    public boolean splitFibonacci(int pos, 
                                   String number, ArrayList < Long > fib)
    {
        if (pos == number.length() && (fib.size() >= 3))
        {
            return true;
        }
        // Define some useful auxiliary variables
        long num = 0;
        // Process indicator
        boolean stop = false;
        // Execute loop until the last character when sequence is fibonacci
        for (int i = pos; i < number.length() && stop == false; ++i)
        {
            // Append digits at the end
            num = (num * 10) + (number.charAt(i) - '0');
            if ((num > Integer.MAX_VALUE) 
                || (number.charAt(pos) == '0' && i > pos))
            {
                // When num size is exceed of integer limit
                stop = true;
            }
            else if (fib.size() > 2 
                     && (num > ((long) fib.get(fib.size() - 1) + 
                     (long) fib.get(fib.size() - 2))))
            {
                // When if consecutive elements are not form of fibonacci series
                stop = true;
            }
            else if (fib.size() < 2 
                     || (num == ((long) fib.get(fib.size() - 1) + 
                     (long) fib.get(fib.size() - 2))))
            {
                // Add number into fibonacci sequence
                fib.add(num);
                if (splitFibonacci(i + 1, number, fib))
                {
                    // When given number are produce fibonacci series
                    return true;
                }
                // Remove added number into fibonacci sequence
                fib.remove(fib.size() - 1);
            }
        }
        // When not valid fibonacci series
        return false;
    }
    public void fibonacciSeries(String number)
    {
        // Display given number
        System.out.print("\n Given number : " + number);
        // Use to collect Fibonacci Sequence
        ArrayList < Long > fib = new ArrayList < Long > ();
        if (splitFibonacci(0, number, fib))
        {
            System.out.print("\n Fibonacci Sequence : " );
            // When fibonacci sequence exist
            // Then display calculated result
            for (int i = 0; i < fib.size(); ++i)
            {
                System.out.print("  " + fib.get(i));
            }
          	System.out.print("\n");
           
        }
        else
        {
            System.out.print("\n Fibonacci Sequence : None\n");
        }
    }
    public static void main(String[] args)
    {
        FibonacciSeries task = new FibonacciSeries();
        // Test Cases
        task.fibonacciSeries("121131427");
        task.fibonacciSeries("10111");
        task.fibonacciSeries("123456");
        task.fibonacciSeries("15611172847");
        task.fibonacciSeries("15611172845");
    }
}

input

 Given number : 121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number : 10111
 Fibonacci Sequence :   10  1  11

 Given number : 123456
 Fibonacci Sequence : None

 Given number : 15611172847
 Fibonacci Sequence : None

 Given number : 15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45
// Include header file
#include <iostream>
#include <string>
#include <limits.h>
#include <vector>

using namespace std;
class FibonacciSeries
{
	public:
		// Find fibonacci sequence in given number when if it is exist
		bool splitFibonacci(int pos, string number, vector < long > &fib)
		{
			if (pos == number.length() && (fib.size() >= 3))
			{
				return true;
			}
			// Define some useful auxiliary variables
			long num = 0;
			// Process indicator
			bool stop = false;
			// Execute loop until the last character when sequence is fibonacci
			for (int i = pos; i < number.length() && stop == false; ++i)
			{
				// Append digits at the end
				num = (num *10) + (number[i] - '0');
				if ((num > INT_MAX) || (number[pos] == '0' && i > pos))
				{
					// When num size is exceed of integer limit
					stop = true;
				}
				else if (fib.size() > 2 
                         && (num > ((long) fib.at(fib.size() - 1) + 
                         (long) fib.at(fib.size() - 2))))
				{
					// When if consecutive elements are not 
                  	// form of fibonacci series
					stop = true;
				}
				else if (fib.size() < 2 
                         || (num == ((long) fib.at(fib.size() - 1) + 
                         (long) fib.at(fib.size() - 2))))
				{
					// Add number into fibonacci sequence
					fib.push_back(num);
					if (this->splitFibonacci(i + 1, number, fib))
					{
						// When given number are produce fibonacci series
						return true;
					}
					// Remove added number into fibonacci sequence
					fib.pop_back();
				}
			}
			// When not valid fibonacci series
			return false;
		}
	void fibonacciSeries(string number)
	{
		// Display given number
		cout << "\n Given number : " << number;
		// Use to collect Fibonacci Sequence
		vector < long > fib;
		if (this->splitFibonacci(0, number, fib))
		{
			cout << "\n Fibonacci Sequence : ";
			// When fibonacci sequence exist
			// Then display calculated result
			for (int i = 0; i < fib.size(); ++i)
			{
				cout << "  " << fib.at(i);
			}
			cout << "\n";
		}
		else
		{
			cout << "\n Fibonacci Sequence : None\n";
		}
	}
};
int main()
{
	FibonacciSeries *task = new FibonacciSeries();
	// Test Cases
	task->fibonacciSeries("121131427");
	task->fibonacciSeries("10111");
	task->fibonacciSeries("123456");
	task->fibonacciSeries("15611172847");
	task->fibonacciSeries("15611172845");
	return 0;
}

input

 Given number : 121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number : 10111
 Fibonacci Sequence :   10  1  11

 Given number : 123456
 Fibonacci Sequence : None

 Given number : 15611172847
 Fibonacci Sequence : None

 Given number : 15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45
// Include namespace system
using System;
using System.Collections.Generic;
public class FibonacciSeries
{
	// Find fibonacci sequence in given number when if it is exist
	public Boolean splitFibonacci(int pos, string number, List < long > fib)
	{
		if (pos == number.Length && (fib.Count >= 3))
		{
			return true;
		}
		// Define some useful auxiliary variables
		long num = 0;
		// Process indicator
		Boolean stop = false;
		// Execute loop until the last character when sequence is fibonacci
		for (int i = pos; i < number.Length && stop == false; ++i)
		{
			// Append digits at the end
			num = (num * 10) + (number[i] - '0');
			if ((num > int.MaxValue) || (number[pos] == '0' && i > pos))
			{
				// When num size is exceed of integer limit
				stop = true;
			}
			else if (fib.Count > 2 
                     && (num > ((long) fib[fib.Count - 1] + 
              			(long) fib[fib.Count - 2])))
			{
				// When if consecutive elements are not form of fibonacci series
				stop = true;
			}
			else if (fib.Count < 2 
                     || (num == ((long) fib[fib.Count - 1] + 
              			(long) fib[fib.Count - 2])))
			{
				// Add number into fibonacci sequence
				fib.Add(num);
				if (this.splitFibonacci(i + 1, number, fib))
				{
					// When given number are produce fibonacci series
					return true;
				}
				// Remove added number into fibonacci sequence
				fib.RemoveAt(fib.Count - 1);
			}
		}
		// When not valid fibonacci series
		return false;
	}
	public void fibonacciSeries(string number)
	{
		// Display given number
		Console.Write("\n Given number : " + number);
		// Use to collect Fibonacci Sequence
		List < long > fib = new List < long > ();
		if (this.splitFibonacci(0, number, fib))
		{
			Console.Write("\n Fibonacci Sequence : ");
			// When fibonacci sequence exist
			// Then display calculated result
			for (int i = 0; i < fib.Count; ++i)
			{
				Console.Write("  " + fib[i]);
			}
			Console.Write("\n");
		}
		else
		{
			Console.Write("\n Fibonacci Sequence : None\n");
		}
	}
	public static void Main(String[] args)
	{
		FibonacciSeries task = new FibonacciSeries();
		// Test Cases
		task.fibonacciSeries("121131427");
		task.fibonacciSeries("10111");
		task.fibonacciSeries("123456");
		task.fibonacciSeries("15611172847");
		task.fibonacciSeries("15611172845");
	}
}

input

 Given number : 121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number : 10111
 Fibonacci Sequence :   10  1  11

 Given number : 123456
 Fibonacci Sequence : None

 Given number : 15611172847
 Fibonacci Sequence : None

 Given number : 15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45
<?php
// Php program for
// Split a numeric string into fibonacci sequence
class FibonacciSeries
{
	// Find fibonacci sequence in given number when if it is exist
	public	function splitFibonacci($pos, $number, &$fib)
	{
		if ($pos == strlen($number) && (count($fib) >= 3))
		{
			return true;
		}
		// Define some useful auxiliary variables
		$num = 0;
		// Process indicator
		$stop = false;
		// Execute loop until the last character when sequence is fibonacci
		for ($i = $pos; $i < strlen($number) && $stop == false; ++$i)
		{
			// Append digits at the end
			$num = ($num * 10) + (ord($number[$i]) - ord('0'));
			if (($num > PHP_INT_MAX) 
                || ($number[$pos] == '0' && $i > $pos))
			{
				// When num size is exceed of integer limit
				$stop = true;
			}
			else if (count($fib) > 2 && ($num > ($fib[count($fib) - 1] + 
                                                 $fib[count($fib) - 2])))
			{
				// When if consecutive elements are not form of fibonacci series
				$stop = true;
			}
			else if (count($fib) < 2 
                     || ($num == ($fib[count($fib) - 1] + 
                                  $fib[count($fib) - 2])))
			{
				// Add number into fibonacci sequence
				$fib[] = $num;
				if ($this->splitFibonacci($i + 1, $number, $fib))
				{
					// When given number are produce fibonacci series
					return true;
				}
				// Remove added number into fibonacci sequence
				array_pop($fib);
			}
		}
		// When not valid fibonacci series
		return false;
	}
	public	function findFibonacciSeries($number)
	{
		// Display given number
		echo("\n Given number : ".$number);
		// Use to collect Fibonacci Sequence
		$fib = array();
		if ($this->splitFibonacci(0, $number, $fib))
		{
			echo("\n Fibonacci Sequence : ");
			// When fibonacci sequence exist
			// Then display calculated result
			for ($i = 0; $i < count($fib); ++$i)
			{
				echo("  ".$fib[$i]);
			}
			echo("\n");
		}
		else
		{
			echo("\n Fibonacci Sequence : None\n");
		}
	}
}

function main()
{
	$task = new FibonacciSeries();
	// Test Cases
	$task->findFibonacciSeries("121131427");
	$task->findFibonacciSeries("10111");
	$task->findFibonacciSeries("123456");
	$task->findFibonacciSeries("15611172847");
	$task->findFibonacciSeries("15611172845");
}
main();

input

 Given number : 121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number : 10111
 Fibonacci Sequence :   10  1  11

 Given number : 123456
 Fibonacci Sequence : None

 Given number : 15611172847
 Fibonacci Sequence : None

 Given number : 15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45
// Node JS program for
// Split a numeric string into fibonacci sequence
class FibonacciSeries
{
	// Find fibonacci sequence in given number when if it is exist
	splitFibonacci(pos, number, fib)
	{
		if (pos == number.length && (fib.length >= 3))
		{
			return true;
		}
		// Define some useful auxiliary variables
		var num = 0;
		// Process indicator
		var stop = false;
		// Execute loop until the last character when sequence is fibonacci
		for (var i = pos; i < number.length && stop == false; ++i)
		{
			// Append digits at the end
			num = (num * 10) + 
                  (number.charAt(i).charCodeAt(0) - '0'.charCodeAt(0));
			if ((num > Number.MAX_VALUE) 
                || (number.charAt(pos) == '0' && i > pos))
			{
				// When num size is exceed of integer limit
				stop = true;
			}
			else if (fib.length > 2 
                     && (num > (fib[fib.length - 1] + 
                                fib[fib.length - 2])))
			{
				// When if consecutive elements are not form of fibonacci series
				stop = true;
			}
			else if (fib.length < 2 || (num == (fib[fib.length - 1] + 
                                                fib[fib.length - 2])))
			{
				// Add number into fibonacci sequence
				fib.push(num);
				if (this.splitFibonacci(i + 1, number, fib))
				{
					// When given number are produce fibonacci series
					return true;
				}
				// Remove added number into fibonacci sequence
				fib.pop();
			}
		}
		// When not valid fibonacci series
		return false;
	}
	fibonacciSeries(number)
	{
		// Display given number
		process.stdout.write("\n Given number : " + number);
		// Use to collect Fibonacci Sequence
		var fib = [];
		if (this.splitFibonacci(0, number, fib))
		{
			process.stdout.write("\n Fibonacci Sequence : ");
			// When fibonacci sequence exist
			// Then display calculated result
			for (var i = 0; i < fib.length; ++i)
			{
				process.stdout.write("  " + fib[i]);
			}
			process.stdout.write("\n");
		}
		else
		{
			process.stdout.write("\n Fibonacci Sequence : None\n");
		}
	}
}

function main()
{
	var task = new FibonacciSeries();
	// Test Cases
	task.fibonacciSeries("121131427");
	task.fibonacciSeries("10111");
	task.fibonacciSeries("123456");
	task.fibonacciSeries("15611172847");
	task.fibonacciSeries("15611172845");
}
main();

input

 Given number : 121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number : 10111
 Fibonacci Sequence :   10  1  11

 Given number : 123456
 Fibonacci Sequence : None

 Given number : 15611172847
 Fibonacci Sequence : None

 Given number : 15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45
import sys
#  Python 3 program for
#  Split a numeric string into fibonacci sequence
class FibonacciSeries :
	#  Find fibonacci sequence in given number when if it is exist
	def splitFibonacci(self, pos, number, fib) :
		if (pos == len(number) and(len(fib) >= 3)) :
			return True
		
		#  Define some useful auxiliary variables
		num = 0
		#  Process indicator
		stop = False
		#  Execute loop until the last character when sequence is fibonacci
		i = pos
		while (i < len(number) and stop == False) :
			#  Append digits at the end
			num = (num * 10) + (ord(number[i]) - ord('0'))
			if ((num > sys.maxsize) or(number[pos] == '0'
					and i > pos)) :
				#  When num size is exceed of integer limit
				stop = True
			elif (len(fib) > 2 and 
                  (num > ( fib[len(fib) - 1] +  fib[len(fib) - 2]))) :
				#  When if consecutive elements are not form of fibonacci series
				stop = True
			elif (len(fib) < 2 or 
                  (num == (fib[len(fib) - 1] +  fib[len(fib) - 2]))) :
				#  Add number into fibonacci sequence
				fib.append(num)
				if (self.splitFibonacci(i + 1, number, fib)) :
					#  When given number are produce fibonacci series
					return True
				
				#  Remove added number into fibonacci sequence
				del fib[len(fib) - 1]
			
			i += 1
		
		#  When not valid fibonacci series
		return False
	
	def fibonacciSeries(self, number) :
		#  Display given number
		print("\n Given number : ", number, end = "")
		#  Use to collect Fibonacci Sequence
		fib = []
		if (self.splitFibonacci(0, number, fib)) :
			print("\n Fibonacci Sequence : ", end = "")
			#  When fibonacci sequence exist
			#  Then display calculated result
			i = 0
			while (i < len(fib)) :
				print(" ", fib[i], end = "")
				i += 1
			
			print(end = "\n")
		else :
			print("\n Fibonacci Sequence : None")
		
	

def main() :
	task = FibonacciSeries()
	#  Test Cases
	task.fibonacciSeries("121131427")
	task.fibonacciSeries("10111")
	task.fibonacciSeries("123456")
	task.fibonacciSeries("15611172847")
	task.fibonacciSeries("15611172845")

if __name__ == "__main__": main()

input

 Given number :  121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number :  10111
 Fibonacci Sequence :   10  1  11

 Given number :  123456
 Fibonacci Sequence : None

 Given number :  15611172847
 Fibonacci Sequence : None

 Given number :  15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45
#  Ruby program for
#  Split a numeric string into fibonacci sequence
class FibonacciSeries 
	#  Find fibonacci sequence in given number when if it is exist
	def splitFibonacci(pos, number, fib) 
		if (pos == number.length && (fib.length >= 3)) 
			return true
		end

		#  Define some useful auxiliary variables
		num = 0
		#  Process indicator
		stop = false
		#  Execute loop until the last character when sequence is fibonacci
		i = pos
		while (i < number.length && stop == false) 
			#  Append digits at the end
			num = (num * 10) + (number[i].ord - '0'.ord)
			if ((num > (2 ** (0. size * 8 - 2))) || 
                (number[pos] == '0' && i > pos)) 
				#  When num size is exceed of integer limit
				stop = true
			elsif (fib.length > 2 && 
                     (num > (fib[fib.length - 1] +  fib[fib.length - 2]))) 
				#  When if consecutive elements are not form of fibonacci series
				stop = true
			elsif (fib.length < 2 || 
                     (num == (fib[fib.length - 1] +  fib[fib.length - 2]))) 
				#  Add number into fibonacci sequence
				fib.push(num)
				if (self.splitFibonacci(i + 1, number, fib)) 
					#  When given number are produce fibonacci series
					return true
				end

				#  Remove added number into fibonacci sequence
				fib.delete_at(fib.length - 1)
			end

			i += 1
		end

		#  When not valid fibonacci series
		return false
	end

	def fibonacciSeries(number) 
		#  Display given number
		print("\n Given number : ", number)
		#  Use to collect Fibonacci Sequence
		fib = []
		if (self.splitFibonacci(0, number, fib)) 
			print("\n Fibonacci Sequence : ")
			#  When fibonacci sequence exist
			#  Then display calculated result
			i = 0
			while (i < fib.length) 
				print("  ", fib[i])
				i += 1
			end
			print("\n")
		else
 
			print("\n Fibonacci Sequence : None\n")
		end

	end

end

def main() 
	task = FibonacciSeries.new()
	#  Test Cases
	task.fibonacciSeries("121131427")
	task.fibonacciSeries("10111")
	task.fibonacciSeries("123456")
	task.fibonacciSeries("15611172847")
	task.fibonacciSeries("15611172845")
end

main()

input

 Given number : 121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number : 10111
 Fibonacci Sequence :   10  1  11

 Given number : 123456
 Fibonacci Sequence : None

 Given number : 15611172847
 Fibonacci Sequence : None

 Given number : 15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45

import scala.collection.mutable._;
// Scala program for
// Split a numeric string into fibonacci sequence
class FibonacciSeries()
{
	// Find fibonacci sequence in given number when if it is exist
	def splitFibonacci(pos: Int, number: String, 
                       fib: ArrayBuffer[Long]): Boolean = {
		if (pos == number.length() && (fib.size >= 3))
		{
			return true;
		}
		// Define some useful auxiliary variables
		var num: Long = 0;
		// Process indicator
		var stop: Boolean = false;
		// Execute loop until the last character when sequence is fibonacci
		var i: Int = pos;
		while (i < number.length() && stop == false)
		{
			// Append digits at the end
			num = (num * 10) + (number.charAt(i).toInt - '0'.toInt);
			if ((num > Int.MaxValue) || (number.charAt(pos) == '0' && i > pos))
			{
				// When num size is exceed of integer limit
				stop = true;
			}
			else if (fib.size > 2 
                     && (num > ( fib(fib.size - 1) +  fib(fib.size - 2))))
			{
				// When if consecutive elements are not form of fibonacci series
				stop = true;
			}
			else if (fib.size < 2 
                     || (num == ( fib(fib.size - 1) +  fib(fib.size - 2))))
			{
				// Add number into fibonacci sequence
				fib += num;
				if (splitFibonacci(i + 1, number, fib))
				{
					// When given number are produce fibonacci series
					return true;
				}
				// Remove added number into fibonacci sequence
				fib.remove(fib.size - 1);
			}
			i += 1;
		}
		// When not valid fibonacci series
		return false;
	}
	def fibonacciSeries(number: String): Unit = {
		// Display given number
		print("\n Given number : " + number);
		// Use to collect Fibonacci Sequence
		var fib: ArrayBuffer[Long] = new ArrayBuffer[Long]();
		if (splitFibonacci(0, number, fib))
		{
			print("\n Fibonacci Sequence : ");
			// When fibonacci sequence exist
			// Then display calculated result
			var i: Int = 0;
			while (i < fib.size)
			{
				print("  " + fib(i));
				i += 1;
			}
			print("\n");
		}
		else
		{
			print("\n Fibonacci Sequence : None\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: FibonacciSeries = new FibonacciSeries();
		// Test Cases
		task.fibonacciSeries("121131427");
		task.fibonacciSeries("10111");
		task.fibonacciSeries("123456");
		task.fibonacciSeries("15611172847");
		task.fibonacciSeries("15611172845");
	}
}

input

 Given number : 121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number : 10111
 Fibonacci Sequence :   10  1  11

 Given number : 123456
 Fibonacci Sequence : None

 Given number : 15611172847
 Fibonacci Sequence : None

 Given number : 15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45
import Foundation;
// Swift 4 program for
// Split a numeric string into fibonacci sequence
class FibonacciSeries
{
	// Find fibonacci sequence in given number when if it is exist
	func splitFibonacci(_ pos: Int, _ n: String, _ fib: inout[Int]) -> Bool
	{
      	var number = Array(n);
		if (pos == number.count && (fib.count >= 3))
		{
			return true;
		}
		// Define some useful auxiliary variables
		var num = 0;
		// Process indicator
		var stop = false;
		// Execute loop until the last character when sequence is fibonacci
		var i = pos;
		while (i < number.count && stop == false)
		{
			// Append digits at the end
			num = (num * 10) + 
              (Int(UnicodeScalar(String(number[i]))!.value) - 
               Int(UnicodeScalar(String("0"))!.value));
			if ((num > Int.max) || (number[pos] == "0" && i > pos))
			{
				// When num size is exceed of integer limit
				stop = true;
			}
			else if (fib.count > 2 
                     && (num > (Int(fib[fib.count - 1]) + 
                                Int(fib[fib.count - 2]))))
			{
				// When if consecutive elements are not form of fibonacci series
				stop = true;
			}
			else if (fib.count < 2 
                     || (num == (Int(fib[fib.count - 1]) + 
                                 Int(fib[fib.count - 2]))))
			{
				// Add number into fibonacci sequence
				fib.append(num);
				if (self.splitFibonacci(i + 1, n, &fib))
				{
					// When given number are produce fibonacci series
					return true;
				}
				// Remove added number into fibonacci sequence
				fib.removeLast();
			}
			i += 1;
		}
		// When not valid fibonacci series
		return false;
	}
	func fibonacciSeries(_ number: String)
	{
		// Display given number
		print("\n Given number : ", number, terminator: "");
		// Use to collect Fibonacci Sequence
		var fib = [Int]();
		if (self.splitFibonacci(0, number, &fib))
		{
			print("\n Fibonacci Sequence : ", terminator: "");
			// When fibonacci sequence exist
			// Then display calculated result
			var i = 0;
			while (i < fib.count)
			{
				print("  ", fib[i], terminator: "");
				i += 1;
			}
			print(terminator: "\n");
		}
		else
		{
			print("\n Fibonacci Sequence : None");
		}
	}
}
func main()
{
	let task = FibonacciSeries();
	// Test Cases
	task.fibonacciSeries("121131427");
	task.fibonacciSeries("10111");
	task.fibonacciSeries("123456");
	task.fibonacciSeries("15611172847");
	task.fibonacciSeries("15611172845");
}
main();

input

 Given number :  121131427
 Fibonacci Sequence :    12   1   13   14   27

 Given number :  10111
 Fibonacci Sequence :    10   1   11

 Given number :  123456
 Fibonacci Sequence : None

 Given number :  15611172847
 Fibonacci Sequence : None

 Given number :  15611172845
 Fibonacci Sequence :    1   5   6   11   17   28   45
// Kotlin program for
// Split a numeric string into fibonacci sequence
class FibonacciSeries
{
	// Find fibonacci sequence in given number when if it is exist
	fun splitFibonacci(pos: Int, 
                        number: String, fib: MutableList < Long > ): Boolean
	{
		if (pos == number.length && (fib.size >= 3))
		{
			return true;
		}
		// Define some useful auxiliary variables
		var num: Long = 0;
		// Process indicator
		var stop: Boolean = false;
		// Execute loop until the last character when sequence is fibonacci
		var i: Int = pos;
		while (i < number.length && stop == false)
		{
			// Append digits at the end
			num = (num * 10) + (number.get(i).toInt() - '0'.toInt());
			if ((num > Int.MAX_VALUE) || (number.get(pos) == '0' && i > pos))
			{
				// When num size is exceed of integer limit
				stop = true;
			}
			else if (fib.size > 2 
                     && (num > (fib[fib.size - 1].toLong() + 
                                fib[fib.size - 2].toLong())))
			{
				// When if consecutive elements are not form of fibonacci series
				stop = true;
			}
			else if (fib.size < 2 
                     || (num == (fib[fib.size - 1].toLong() + 
                                 fib[fib.size - 2].toLong())))
			{
				// Add number into fibonacci sequence
				fib.add(num);
				if (this.splitFibonacci(i + 1, number, fib))
				{
					// When given number are produce fibonacci series
					return true;
				}
				// Remove added number into fibonacci sequence
				fib.removeAt(fib.size - 1);
			}
			i += 1;
		}
		// When not valid fibonacci series
		return false;
	}
	fun fibonacciSeries(number: String): Unit
	{
		// Display given number
		print("\n Given number : " + number);
		// Use to collect Fibonacci Sequence
		var fib: MutableList < Long > = mutableListOf < Long > ();
		if (this.splitFibonacci(0, number, fib))
		{
			print("\n Fibonacci Sequence : ");
			// When fibonacci sequence exist
			// Then display calculated result
			var i: Int = 0;
			while (i < fib.size)
			{
				print("  " + fib[i]);
				i += 1;
			}
			print("\n");
		}
		else
		{
			print("\n Fibonacci Sequence : None\n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: FibonacciSeries = FibonacciSeries();
	// Test Cases
	task.fibonacciSeries("121131427");
	task.fibonacciSeries("10111");
	task.fibonacciSeries("123456");
	task.fibonacciSeries("15611172847");
	task.fibonacciSeries("15611172845");
}

input

 Given number : 121131427
 Fibonacci Sequence :   12  1  13  14  27

 Given number : 10111
 Fibonacci Sequence :   10  1  11

 Given number : 123456
 Fibonacci Sequence : None

 Given number : 15611172847
 Fibonacci Sequence : None

 Given number : 15611172845
 Fibonacci Sequence :   1  5  6  11  17  28  45

Time Complexity

The time complexity of this solution heavily depends on the input and the actual sequence that forms. In the worst case, where the program needs to explore all possible combinations of splitting the string, the time complexity can be exponential. However, in practice, the number of recursive calls and combinations tried is often much smaller due to early stopping conditions. Therefore, the average-case time complexity would be lower than the worst case.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post