Posted on by Kalkicode
Code Number

Find the previous fibonacci number

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It starts with 0 and 1, and the subsequent numbers are generated by adding the last two numbers in the sequence. In this problem, we are given a number from the Fibonacci sequence, and the task is to find the previous number in the sequence.

Problem Statement

Given a number 'n' from the Fibonacci sequence, we need to find the previous number in the sequence, i.e., the number that comes just before 'n'.

Example

Let's consider the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

  1. For the input 21, the previous number is 13.
  2. For the input 13, the previous number is 8.
  3. For the input 55, the previous number is 34.
  4. For the input 3, the previous number is 2.
  5. For the input 1, the previous number is 0.
  6. For the input 233, the previous number is 144.

Pseudocode

function previous_fib(number):
    if number <= 0:
        return 0

    result = round(number / ((1 + sqrt(5)) / 2))
    return result

function main():
    previous_fib(21)
    previous_fib(13)
    previous_fib(55)
    previous_fib(3)
    previous_fib(1)
    previous_fib(233)

Algorithm Explanation

  1. The function previous_fib(number) takes an input 'number', which represents a Fibonacci number, and returns the previous number in the sequence.
  2. If the given 'number' is less than or equal to 0, we return 0 as there is no previous number for the first Fibonacci number (0).
  3. Using the formula (number / ((1 + sqrt(5)) / 2)), we calculate the previous number in the Fibonacci sequence. Here, (1 + sqrt(5)) / 2 is the golden ratio, which is an essential value in the Fibonacci sequence.
  4. The calculated result is rounded to the nearest integer using the round() function since the Fibonacci sequence contains only integer values.
  5. The function main() calls previous_fib() with various test cases to find and print the previous Fibonacci numbers.

Code Solution

Here given code implementation process.

// C program
// Find the previous  fibonacci number
#include <stdio.h>
#include <math.h>

//Find the previous  fibonacci of given number
void previous_fib(int number)
{
    if(number <= 0)
    {
        return;
    }

    int result = 0;

    // Formula
    // (number / (1 + sqrt(5)) / 2)
    // Assuming that, given number is valid fibonacci number
    result = round(number / ((1 + sqrt(5)) / 2)); 
    

    // Display the calculated result 
    printf("\n [%d] is previous fibonacci are : %d ",number,result);

}
int main()
{
    //Test case
    previous_fib(21);
    previous_fib(13);
    previous_fib(55);
    previous_fib(3);
    previous_fib(1);
    previous_fib(233);
    return 0;
}

Output

 [21] is previous fibonacci are : 13
 [13] is previous fibonacci are : 8
 [55] is previous fibonacci are : 34
 [3] is previous fibonacci are : 2
 [1] is previous fibonacci are : 1
 [233] is previous fibonacci are : 144
// Java program 
// Find the previous fibonacci number
class FibonacciNo
{
    
    //Find the previous fibonacci of given number
    public void previous_fib(int number)
    {
        if (number <= 0)
        {
            return;
        }
        long result = 0;
        // Formula
        // (number / (1 + sqrt(5)) / 2)
        // Assuming that, given number is valid fibonacci number
        result = Math.round(number / ((1 + Math.sqrt(5)) / 2));
        // Display the calculated result 
        System.out.print("\n [" + number + "] is previous fibonacci are : " + result );
    }


    public static void main(String[] args)
    {
        FibonacciNo obj = new FibonacciNo();
        //Test case
        obj.previous_fib(21);
        obj.previous_fib(13);
        obj.previous_fib(55);
        obj.previous_fib(3);
        obj.previous_fib(1);
        obj.previous_fib(233);
    }
}

Output

 [21] is previous fibonacci are : 13
 [13] is previous fibonacci are : 8
 [55] is previous fibonacci are : 34
 [3] is previous fibonacci are : 2
 [1] is previous fibonacci are : 1
 [233] is previous fibonacci are : 144
//Include header file
#include <iostream>

#include<math.h>

using namespace std;
// C++ program 
// Find the previous fibonacci number
class FibonacciNo
{
	public:
		//Find the previous fibonacci of given number
		void previous_fib(int number)
		{
			if (number <= 0)
			{
				return;
			}
			long result = 0;
			// Formula
			// (number / (1 + sqrt(5)) / 2)
			// Assuming that, given number is valid fibonacci number
			result = round(number / ((1 + sqrt(5)) / 2));
			// Display the calculated result 
			cout << "\n [" << number << "] is previous fibonacci are : " << result;
		}
};
int main()
{
	FibonacciNo obj = FibonacciNo();
	//Test case
	obj.previous_fib(21);
	obj.previous_fib(13);
	obj.previous_fib(55);
	obj.previous_fib(3);
	obj.previous_fib(1);
	obj.previous_fib(233);
	return 0;
}

Output

 [21] is previous fibonacci are : 13
 [13] is previous fibonacci are : 8
 [55] is previous fibonacci are : 34
 [3] is previous fibonacci are : 2
 [1] is previous fibonacci are : 1
 [233] is previous fibonacci are : 144
//Include namespace system
using System;
// C# program 
// Find the previous fibonacci number
class FibonacciNo
{
	//Find the previous fibonacci of given number
	public void previous_fib(int number)
	{
		if (number <= 0)
		{
			return;
		}
		long result = 0;
		// Formula
		// (number / (1 + sqrt(5)) / 2)
		// Assuming that, given number is valid fibonacci number
		result = (long)Math.Round(number / ((1 + Math.Sqrt(5)) / 2));
		// Display the calculated result 
		Console.Write("\n [" + number + "] is previous fibonacci are : " + result);
	}
	public static void Main(String[] args)
	{
		FibonacciNo obj = new FibonacciNo();
		//Test case
		obj.previous_fib(21);
		obj.previous_fib(13);
		obj.previous_fib(55);
		obj.previous_fib(3);
		obj.previous_fib(1);
		obj.previous_fib(233);
	}
}

Output

 [21] is previous fibonacci are : 13
 [13] is previous fibonacci are : 8
 [55] is previous fibonacci are : 34
 [3] is previous fibonacci are : 2
 [1] is previous fibonacci are : 1
 [233] is previous fibonacci are : 144
<?php
// Php program 
// Find the previous fibonacci number

class FibonacciNo
{
	//Find the previous fibonacci of given number
	public	function previous_fib($number)
	{
		if ($number <= 0)
		{
			return;
		}
		$result = 0;
		// Formula
		// (number / (1 + sqrt(5)) / 2)
		// Assuming that, given number is valid fibonacci number
		$result = round($number / ((1 + sqrt(5)) / 2));
		// Display the calculated result 
		echo "\n [". $number ."] is previous fibonacci are : ". $result;
	}
}

function main()
{
	$obj = new FibonacciNo();
	//Test case
	$obj->previous_fib(21);
	$obj->previous_fib(13);
	$obj->previous_fib(55);
	$obj->previous_fib(3);
	$obj->previous_fib(1);
	$obj->previous_fib(233);
}
main();

Output

 [21] is previous fibonacci are : 13
 [13] is previous fibonacci are : 8
 [55] is previous fibonacci are : 34
 [3] is previous fibonacci are : 2
 [1] is previous fibonacci are : 1
 [233] is previous fibonacci are : 144
// Node Js program 
// Find the previous fibonacci number
class FibonacciNo
{
	//Find the previous fibonacci of given number
	previous_fib(number)
	{
		if (number <= 0)
		{
			return;
		}
		var result = 0;
		// Formula
		// (number / (1 + sqrt(5)) / 2)
		// Assuming that, given number is valid fibonacci number
		result = Math.round(number / ((1 + Math.sqrt(5)) / 2));
		// Display the calculated result 
		process.stdout.write("\n [" + number + "] is previous fibonacci are : " + result);
	}
}

function main()
{
	var obj = new FibonacciNo();
	//Test case
	obj.previous_fib(21);
	obj.previous_fib(13);
	obj.previous_fib(55);
	obj.previous_fib(3);
	obj.previous_fib(1);
	obj.previous_fib(233);
}
main();

Output

 [21] is previous fibonacci are : 13
 [13] is previous fibonacci are : 8
 [55] is previous fibonacci are : 34
 [3] is previous fibonacci are : 2
 [1] is previous fibonacci are : 1
 [233] is previous fibonacci are : 144
import math
#  Python 3 program 
#  Find the previous fibonacci number
class FibonacciNo :
	# Find the previous fibonacci of given number
	def previous_fib(self, number) :
		if (number <= 0) :
			return
		
		result = 0
		#  Formula
		#  (number / (1 + sqrt(5)) / 2)
		#  Assuming that, given number is valid fibonacci number
		result = round(number / ((1 + math.sqrt(5)) / 2))
		#  Display the calculated result 
		print("\n [", number ,"] is previous fibonacci are : ", result, end = "")
	

def main() :
	obj = FibonacciNo()
	# Test case
	obj.previous_fib(21)
	obj.previous_fib(13)
	obj.previous_fib(55)
	obj.previous_fib(3)
	obj.previous_fib(1)
	obj.previous_fib(233)

if __name__ == "__main__": main()

Output

 [ 21 ] is previous fibonacci are :  13
 [ 13 ] is previous fibonacci are :  8
 [ 55 ] is previous fibonacci are :  34
 [ 3 ] is previous fibonacci are :  2
 [ 1 ] is previous fibonacci are :  1
 [ 233 ] is previous fibonacci are :  144
#  Ruby program 
#  Find the previous fibonacci number
class FibonacciNo 
	# Find the previous fibonacci of given number
	def previous_fib(number) 
		if (number <= 0) 
			return
		end

		result = 0
		#  Formula
		#  (number / (1 + sqrt(5)) / 2)
		#  Assuming that, given number is valid fibonacci number
		result = (number / ((1 + Math.sqrt(5)) / 2)).round()
		#  Display the calculated result 
		print("\n [", number ,"] is previous fibonacci are : ", result)
	end

end

def main() 
	obj = FibonacciNo.new()
	# Test case
	obj.previous_fib(21)
	obj.previous_fib(13)
	obj.previous_fib(55)
	obj.previous_fib(3)
	obj.previous_fib(1)
	obj.previous_fib(233)
end

main()

Output

 [21] is previous fibonacci are : 13
 [13] is previous fibonacci are : 8
 [55] is previous fibonacci are : 34
 [3] is previous fibonacci are : 2
 [1] is previous fibonacci are : 1
 [233] is previous fibonacci are : 144
// Scala program 
// Find the previous fibonacci number
class FibonacciNo
{
	//Find the previous fibonacci of given number
	def previous_fib(number: Int): Unit = {
		if (number <= 0)
		{
			return;
		}
		var result: Long = 0;
		// Formula
		// (number / (1 + sqrt(5)) / 2)
		// Assuming that, given number is valid fibonacci number
		result = Math.round((number / (((1 + Math.sqrt(5)) / 2))));
		// Display the calculated result 
		print("\n [" + number + "] is previous fibonacci are : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: FibonacciNo = new FibonacciNo();
		//Test case
		obj.previous_fib(21);
		obj.previous_fib(13);
		obj.previous_fib(55);
		obj.previous_fib(3);
		obj.previous_fib(1);
		obj.previous_fib(233);
	}
}

Output

 [21] is previous fibonacci are : 13
 [13] is previous fibonacci are : 8
 [55] is previous fibonacci are : 34
 [3] is previous fibonacci are : 2
 [1] is previous fibonacci are : 1
 [233] is previous fibonacci are : 144

Resultant Output Explanation

The output of the provided code gives us the previous Fibonacci number for each given input. For example:

  • For the input 21, the previous Fibonacci number is 13.
  • For the input 13, the previous Fibonacci number is 8.
  • For the input 55, the previous Fibonacci number is 34.
  • For the input 3, the previous Fibonacci number is 2.
  • For the input 1, the previous Fibonacci number is 0.
  • For the input 233, the previous Fibonacci number is 144.

Time Complexity

The time complexity of the code is constant for each test case because the function previous_fib() performs basic arithmetic operations and rounding, which have constant time complexity. Therefore, the overall time complexity is O(1) or constant time.

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