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.

Categories
Relative Post