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]:
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
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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
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
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)
{
// Test Cases
}
}``````

#### 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()
{
// Test Cases
}
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()
{
// Test Cases
}
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() :
#  Test Cases

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()
#  Test Cases
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
}
}``````

#### 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()
{
// Test Cases
}
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
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
{
// Test Cases
}``````

#### 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.

Categories
Relative Post