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
- The
splitFibonacci
function takes the current positionpos
in the numeric string, the stringnumber
itself, and an ArrayListfib
to store the Fibonacci sequence. - 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.
- Initialize
num
as 0 andstop
as false. - Loop through the string from the current position to the end.
- Append digits to
num
and check for conditions that would stop the loop: ifnum
exceeds the maximum integer value or if a leading zero is encountered. - Check if the current subsequence does not follow the Fibonacci property or if it matches the next Fibonacci number in the sequence.
- 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. - If no valid sequence is found, return false.
- The
fibonacciSeries
function initializes thefib
ArrayList and callssplitFibonacci
. 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.
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