Posted on by Kalkicode
Code Number

Find Nth even fibonacci number

The given problem is to find the Nth even Fibonacci number in the Fibonacci series. The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The first few numbers in the Fibonacci series are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.

Problem Statement

Given an integer N, the task is to find the Nth even number in the Fibonacci series.

Explanation with Suitable Example

Let's take N = 6 as an example. We need to find the 6th even Fibonacci number.

The Fibonacci series starts with 0 and 1, so the first even number is 0 (0th index), the second even number is 2 (1st index), and the third even number is 8 (2nd index). Now, to find the 6th even number, we can recursively calculate it using the formula even_fib_element(n) = 4 * even_fib_element(n-1) + even_fib_element(n-2).

Standard Pseudocode

function even_fib_element(n):
    if n < 1:
        return n
    else if n == 1:
        return 2
    return (4 * even_fib_element(n - 1)) + even_fib_element(n - 2)

function fibonacci_node(n_th):
    if n_th <= 0:
        return
    result = even_fib_element(n_th)
    print(n_th + "-th Even Fibonacci element is:", result)

Algorithm with Explanation

  1. The even_fib_element(n) function is a recursive function to find the Nth even Fibonacci number. It takes an integer n as input and returns the Nth even Fibonacci number.

  2. If n is less than 1, it means we need to find the 0th or negative even Fibonacci number, which is equal to n. So, we return n.

  3. If n is 1, it means we need to find the 2nd even Fibonacci number, which is 2. So, we return 2.

  4. For any n greater than 1, we use the recursive formula even_fib_element(n) = 4 * even_fib_element(n-1) + even_fib_element(n-2) to find the Nth even Fibonacci number.

  5. The fibonacci_node(n_th) function is used to handle the request of finding the Nth even Fibonacci number.

  6. If n_th is less than or equal to 0, it is an invalid input, and we return from the function.

  7. Otherwise, we call the even_fib_element() function with n_th as the input and store the result in the result variable.

  8. Finally, we print the n_th-th Even Fibonacci element along with the calculated result.

Code Solution

Here given code implementation process.

// C program
// Find Nth even fibonacci number
#include <stdio.h>

//Find n-th Even Number in a fibonacci series
long long int even_fib_element(int n)
{
	if (n < 1)
	{
		//When n is less than 1
		return n;
	}
	else if (n == 1)
	{
		//When n is equal to 1
		return 2;
	}
	// Recursively detect nth even element
	return ((4 * even_fib_element(n - 1)) + even_fib_element(n - 2));
}
//This function are handling the request of finding nth Even Number 
void fibonacci_node(int n_th)
{
	if (n_th <= 0)
	{
		return;
	}
	long long int result = even_fib_element(n_th);
	//Display calculated result
	printf("\n %d-th Even fibonacci element is : %lld ", n_th, result);
}
int main()
{
	//Test case
	fibonacci_node(2);
	fibonacci_node(9);
	fibonacci_node(6);
	fibonacci_node(4);
	fibonacci_node(7);
	return 0;
}

Output

 2-th Even fibonacci element is : 8
 9-th Even fibonacci element is : 196418
 6-th Even fibonacci element is : 2584
 4-th Even fibonacci element is : 144
 7-th Even fibonacci element is : 10946
// Java program 
// Find Nth Odd fibonacci number
class FibonacciNo
{
	//Find n-th Even Number in a fibonacci series
	public long even_fib_element(int n)
	{
		if (n < 1)
		{
			//When n is less than 1
			return n;
		}
		else if (n == 1)
		{
			//When n is equal to 1
			return 2;
		}
		// Recursively detect nth even element
		return ((4 * even_fib_element(n - 1)) + even_fib_element(n - 2));
	}
	//This function are handling the request of finding nth Even Number 
	public void fibonacci_node(int n_th)
	{
		if (n_th <= 0)
		{
			return;
		}
		long result = even_fib_element(n_th);
		//Display calculated result
		System.out.print("\n " + n_th + "-th Even fibonacci element is : " + result + " ");
	}
	public static void main(String[] args)
	{
		FibonacciNo obj = new FibonacciNo();
		//Test case
		obj.fibonacci_node(2);
		obj.fibonacci_node(9);
		obj.fibonacci_node(6);
		obj.fibonacci_node(4);
		obj.fibonacci_node(7);
	}
}

Output

 2-th Even fibonacci element is : 8
 9-th Even fibonacci element is : 196418
 6-th Even fibonacci element is : 2584
 4-th Even fibonacci element is : 144
 7-th Even fibonacci element is : 10946
//Include header file
#include <iostream>

using namespace std;
// C++ program 
// Find Nth Odd fibonacci number
class FibonacciNo
{
	public:
		//Find n-th Even Number in a fibonacci series
		long even_fib_element(int n)
		{
			if (n < 1)
			{
				//When n is less than 1
				return n;
			}
			else if (n == 1)
			{
				//When n is equal to 1
				return 2;
			}
			// Recursively detect nth even element
			return ((4 *this->even_fib_element(n - 1)) + this->even_fib_element(n - 2));
		}
	//This function are handling the request of finding nth Even Number 
	void fibonacci_node(int n_th)
	{
		if (n_th <= 0)
		{
			return;
		}
		long result = this->even_fib_element(n_th);
		//Display calculated result
		cout << "\n " << n_th << "-th Even fibonacci element is : " << result << " ";
	}
};
int main()
{
	FibonacciNo obj = FibonacciNo();
	//Test case
	obj.fibonacci_node(2);
	obj.fibonacci_node(9);
	obj.fibonacci_node(6);
	obj.fibonacci_node(4);
	obj.fibonacci_node(7);
	return 0;
}

Output

 2-th Even fibonacci element is : 8
 9-th Even fibonacci element is : 196418
 6-th Even fibonacci element is : 2584
 4-th Even fibonacci element is : 144
 7-th Even fibonacci element is : 10946
//Include namespace system
using System;

// C# program 
// Find Nth Odd fibonacci number

class FibonacciNo
{
	//Find n-th Even Number in a fibonacci series
	public long even_fib_element(int n)
	{
		if (n < 1)
		{
			//When n is less than 1
			return n;
		}
		else if (n == 1)
		{
			//When n is equal to 1
			return 2;
		}
		// Recursively detect nth even element
		return ((4 * even_fib_element(n - 1)) + even_fib_element(n - 2));
	}
	//This function are handling the request of finding nth Even Number 
	public void fibonacci_node(int n_th)
	{
		if (n_th <= 0)
		{
			return;
		}
		long result = even_fib_element(n_th);
		//Display calculated result
		Console.Write("\n " + n_th + "-th Even fibonacci element is : " + result + " ");
	}
	public static void Main(String[] args)
	{
		FibonacciNo obj = new FibonacciNo();
		//Test case
		obj.fibonacci_node(2);
		obj.fibonacci_node(9);
		obj.fibonacci_node(6);
		obj.fibonacci_node(4);
		obj.fibonacci_node(7);
	}
}

Output

 2-th Even fibonacci element is : 8
 9-th Even fibonacci element is : 196418
 6-th Even fibonacci element is : 2584
 4-th Even fibonacci element is : 144
 7-th Even fibonacci element is : 10946
<?php
// Php program 
// Find Nth Odd fibonacci number

class FibonacciNo
{
	//Find n-th Even Number in a fibonacci series
	public	function even_fib_element($n)
	{
		if ($n < 1)
		{
			//When n is less than 1
			return $n;
		}
		else if ($n == 1)
		{
			//When n is equal to 1
			return 2;
		}
		// Recursively detect nth even element
		return ((4 * $this->even_fib_element($n - 1)) + $this->even_fib_element($n - 2));
	}
	//This function are handling the request of finding nth Even Number 
	public	function fibonacci_node($n_th)
	{
		if ($n_th <= 0)
		{
			return;
		}
		$result = $this->even_fib_element($n_th);
		//Display calculated result
		echo "\n ". $n_th ."-th Even fibonacci element is : ". $result ." ";
	}
}

function main()
{
	$obj = new FibonacciNo();
	//Test case
	$obj->fibonacci_node(2);
	$obj->fibonacci_node(9);
	$obj->fibonacci_node(6);
	$obj->fibonacci_node(4);
	$obj->fibonacci_node(7);
}
main();

Output

 2-th Even fibonacci element is : 8
 9-th Even fibonacci element is : 196418
 6-th Even fibonacci element is : 2584
 4-th Even fibonacci element is : 144
 7-th Even fibonacci element is : 10946
// Node Js program 
// Find Nth Odd fibonacci number
class FibonacciNo
{
	//Find n-th Even Number in a fibonacci series
	even_fib_element(n)
	{
		if (n < 1)
		{
			//When n is less than 1
			return n;
		}
		else if (n == 1)
		{
			//When n is equal to 1
			return 2;
		}
		// Recursively detect nth even element
		return ((4 * this.even_fib_element(n - 1)) + this.even_fib_element(n - 2));
	}
	//This function are handling the request of finding nth Even Number 
	fibonacci_node(n_th)
	{
		if (n_th <= 0)
		{
			return;
		}
		var result = this.even_fib_element(n_th);
		//Display calculated result
		process.stdout.write("\n " + n_th + "-th Even fibonacci element is : " + result + " ");
	}
}

function main()
{
	var obj = new FibonacciNo();
	//Test case
	obj.fibonacci_node(2);
	obj.fibonacci_node(9);
	obj.fibonacci_node(6);
	obj.fibonacci_node(4);
	obj.fibonacci_node(7);
}
main();

Output

 2-th Even fibonacci element is : 8
 9-th Even fibonacci element is : 196418
 6-th Even fibonacci element is : 2584
 4-th Even fibonacci element is : 144
 7-th Even fibonacci element is : 10946
#  Python 3 program 
#  Find Nth Odd fibonacci number
class FibonacciNo :
	# Find n-th Even Number in a fibonacci series
	def even_fib_element(self, n) :
		if (n < 1) :
			# When n is less than 1
			return n
		
		elif(n == 1) :
			# When n is equal to 1
			return 2
		
		#  Recursively detect nth even element
		return ((4 * self.even_fib_element(n - 1)) + self.even_fib_element(n - 2))
	
	# This function are handling the request of finding nth Even Number 
	def fibonacci_node(self, n_th) :
		if (n_th <= 0) :
			return
		
		result = self.even_fib_element(n_th)
		# Display calculated result
		print("\n ", n_th ,"-th Even fibonacci element is : ", result ," ", end = "")
	

def main() :
	obj = FibonacciNo()
	# Test case
	obj.fibonacci_node(2)
	obj.fibonacci_node(9)
	obj.fibonacci_node(6)
	obj.fibonacci_node(4)
	obj.fibonacci_node(7)

if __name__ == "__main__": main()

Output

  2 -th Even fibonacci element is :  8
  9 -th Even fibonacci element is :  196418
  6 -th Even fibonacci element is :  2584
  4 -th Even fibonacci element is :  144
  7 -th Even fibonacci element is :  10946
#  Ruby program 
#  Find Nth Odd fibonacci number
class FibonacciNo 
	# Find n-th Even Number in a fibonacci series
	def even_fib_element(n) 
		if (n < 1) 
			# When n is less than 1
			return n
		elsif(n == 1) 
			# When n is equal to 1
			return 2
		end

		#  Recursively detect nth even element
		return ((4 * self.even_fib_element(n - 1)) + self.even_fib_element(n - 2))
	end

	# This function are handling the request of finding nth Even Number 
	def fibonacci_node(n_th) 
		if (n_th <= 0) 
			return
		end

		result = self.even_fib_element(n_th)
		# Display calculated result
		print("\n ", n_th ,"-th Even fibonacci element is : ", result ," ")
	end

end

def main() 
	obj = FibonacciNo.new()
	# Test case
	obj.fibonacci_node(2)
	obj.fibonacci_node(9)
	obj.fibonacci_node(6)
	obj.fibonacci_node(4)
	obj.fibonacci_node(7)
end

main()

Output

 2-th Even fibonacci element is : 8 
 9-th Even fibonacci element is : 196418 
 6-th Even fibonacci element is : 2584 
 4-th Even fibonacci element is : 144 
 7-th Even fibonacci element is : 10946 
// Scala program 
// Find Nth Odd fibonacci number
class FibonacciNo
{
	//Find n-th Even Number in a fibonacci series
	def even_fib_element(n: Int): Long = {
		if (n < 1)
		{
			//When n is less than 1
			return n;
		}
		else if (n == 1)
		{
			//When n is equal to 1
			return 2;
		}
		// Recursively detect nth even element
		return ((4 * even_fib_element(n - 1)) + even_fib_element(n - 2));
	}
	//This function are handling the request of finding nth Even Number 
	def fibonacci_node(n_th: Int): Unit = {
		if (n_th <= 0)
		{
			return;
		}
		var result: Long = even_fib_element(n_th);
		//Display calculated result
		print("\n " + n_th + "-th Even fibonacci element is : " + result + " ");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: FibonacciNo = new FibonacciNo();
		//Test case
		obj.fibonacci_node(2);
		obj.fibonacci_node(9);
		obj.fibonacci_node(6);
		obj.fibonacci_node(4);
		obj.fibonacci_node(7);
	}
}

Output

 2-th Even fibonacci element is : 8
 9-th Even fibonacci element is : 196418
 6-th Even fibonacci element is : 2584
 4-th Even fibonacci element is : 144
 7-th Even fibonacci element is : 10946
// Swift 4 program 
// Find Nth Odd fibonacci number
class FibonacciNo
{
	//Find n-th Even Number in a fibonacci series
	func even_fib_element(_ n: Int) -> Int
	{
		if (n < 1)
		{
			//When n is less than 1
			return n;
		}
		else if (n == 1)
		{
			//When n is equal to 1
			return 2;
		}
		// Recursively detect nth even element
		return ((4 * self.even_fib_element(n - 1)) + self.even_fib_element(n - 2));
	}
	//This function are handling the request of finding nth Even Number 
	func fibonacci_node(_ n_th: Int)
	{
		if (n_th <= 0)
		{
			return;
		}
		let result: Int = self.even_fib_element(n_th);
		//Display calculated result
		print("\n ", n_th ,"-th Even fibonacci element is : ", result ," ", terminator: "");
	}
}
func main()
{
	let obj: FibonacciNo = FibonacciNo();
	//Test case
	obj.fibonacci_node(2);
	obj.fibonacci_node(9);
	obj.fibonacci_node(6);
	obj.fibonacci_node(4);
	obj.fibonacci_node(7);
}
main();

Output

  2 -th Even fibonacci element is :  8
  9 -th Even fibonacci element is :  196418
  6 -th Even fibonacci element is :  2584
  4 -th Even fibonacci element is :  144
  7 -th Even fibonacci element is :  10946

Resultant Output Explanation

After running the code with the given test cases, the output is as follows:

2-th Even Fibonacci element is : 8
9-th Even Fibonacci element is : 196418
6-th Even Fibonacci element is : 2584
4-th Even Fibonacci element is : 144
7-th Even Fibonacci element is : 10946

Time Complexity

The time complexity of the given code can be analyzed based on the recursion depth. Let n be the input to the function even_fib_element(n).

The recurrence relation for the time complexity can be expressed as:

T(n) = T(n-1) + T(n-2) + O(1)

The recursive calls form a binary tree, and at each level, the number of nodes doubles. So the height of the tree is log(n), and the number of nodes in the tree is approximately 2^(log(n)) = n.

Therefore, the time complexity of the even_fib_element() function is O(2^n). The main function calls this function for each test case, so the overall time complexity of the program is O(k * 2^n), where k is the number of test cases.

Note: The given code is not efficient for large values of n due to the exponential time complexity. To find even Fibonacci numbers efficiently, other approaches like iterative methods or memoization can be employed.

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