Find Nth Odd fibonacci number

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. An interesting variant is the Odd Fibonacci sequence, which includes only the odd numbers from the original Fibonacci sequence. In this article, we will explore how to find the Nth element in the Odd Fibonacci series using a program.

Problem Statement

Given a positive integer N, we need to find the Nth odd element in the Fibonacci series.

Explanation with Suitable Example: Let's consider the original Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13, ... The Odd Fibonacci series includes only the odd numbers from the original series: 1, 1, 3, 5, 13, ...

For instance, when N = 6, we need to find the 6th odd element in the Odd Fibonacci series, which is 13.

Standard Pseudocode

// Function to find the Nth odd element in the Fibonacci series
function odd_fibonacci(N):
    // Check if N is valid (greater than 0)
    if N <= 0:
        return "Invalid input"

    // Calculate the location of Nth odd element in the Fibonacci series
    n = (3 * N + 1) / 2

    // Initialize variables for Fibonacci series calculation
    result = 0
    a = 0
    b = 1

    // Loop to find the Nth element in Fibonacci series
    for i from 1 to n:
        result = a
        b = b + a
        a = b - a

    // Return the Nth odd Fibonacci element
    return result

1. Start
2. Input the value of N (the position of the odd Fibonacci element to be found)
3. If N is less than or equal to 0, return
4. Calculate the location of the Nth odd element: n = (3 * N + 1) / 2
5. Initialize variables: result = 0, a = 0, b = 1
6. Loop i from 1 to n a. Set result = a b. Set b = b + a c. Set a = b - a
7. Print the N-th Odd Fibonacci element: result
8. End

Algorithm Explanation

1. We first check if N is valid (greater than 0) and if not, we return since there's no valid output for invalid N.
2. To find the Nth odd element, we calculate its position in the original Fibonacci series, which is (3 * N + 1) / 2. This is because every third element in the Fibonacci series is odd.
3. We then initialize variables a and b to 0 and 1, respectively, to start the Fibonacci sequence.
4. We loop from 1 to n, updating a and b in each iteration to calculate the Nth element in the Fibonacci series.
5. After the loop, the value of 'result' will be the Nth element in the Odd Fibonacci series.
6. Finally, we print the result as the Nth odd element.

Code Solution

Here given code implementation process.

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

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

//Find the nth odd element in fibonacci series
void odd_fibonacci(int n_th)
{
	if (n_th <= 0)
	{
		return;
	}
	//Get location of nth odd element in fibonacci series
	int n = (3 * n_th + 1) / 2;
	//Define resultant variable
	int result = 0;
	int a = 0;
	int b = 1;
	//Find nth element in fibonacci serie
	for (int i = 1; i <= n; i++)
	{
		result = a;
		b = b + a;
		a = b - a;
	}
	//Display the calculated result result
	printf("\n %d-th Odd fibonacci element is : %d ", n_th, result);
}
int main()
{
	//Test case
	odd_fibonacci(2);
	odd_fibonacci(9);
	odd_fibonacci(6);
	odd_fibonacci(4);
	odd_fibonacci(7);
	return 0;
}

 2-th Odd fibonacci element is : 1
 9-th Odd fibonacci element is : 233
 6-th Odd fibonacci element is : 21
 4-th Odd fibonacci element is : 5
 7-th Odd fibonacci element is : 55

// Java program 
// Find nth odd fibonacci number
class FibonacciNo
{
	//Find the nth odd element in fibonacci series
	public void odd_fibonacci(int n_th)
	{
		if (n_th <= 0)
		{
			return;
		}
		//Get location of nth odd element in fibonacci series
		int n = (3 * n_th + 1) / 2;
		//Define resultant variable
		int result = 0;
		int a = 0;
		int b = 1;
		//Find nth element in fibonacci serie
		for (int i = 1; i <= n; i++)
		{
			result = a;
			b = b + a;
			a = b - a;
		}
		//Display the calculated result result
		System.out.print("\n " + n_th + "-th Odd fibonacci element is : " + result );
	}
	public static void main(String[] args)
	{
		FibonacciNo obj = new FibonacciNo();
		//Test case
		obj.odd_fibonacci(2);
		obj.odd_fibonacci(9);
		obj.odd_fibonacci(6);
		obj.odd_fibonacci(4);
		obj.odd_fibonacci(7);
	}
}

 2-th Odd fibonacci element is : 1
 9-th Odd fibonacci element is : 233
 6-th Odd fibonacci element is : 21
 4-th Odd fibonacci element is : 5
 7-th Odd fibonacci element is : 55

//Include header file
#include <iostream>
using namespace std;

// C++ program 
// Find nth odd fibonacci number

class FibonacciNo
{
	public:
		//Find the nth odd element in fibonacci series
		void odd_fibonacci(int n_th)
		{
			if (n_th <= 0)
			{
				return;
			}
			//Get location of nth odd element in fibonacci series
			int n = (3 *n_th + 1) / 2;
			//Define resultant variable
			int result = 0;
			int a = 0;
			int b = 1;
			//Find nth element in fibonacci serie
			for (int i = 1; i <= n; i++)
			{
				result = a;
				b = b + a;
				a = b - a;
			}
			//Display the calculated result result
			cout << "\n " << n_th << "-th Odd fibonacci element is : " << result;
		}
};
int main()
{
	FibonacciNo obj = FibonacciNo();
	//Test case
	obj.odd_fibonacci(2);
	obj.odd_fibonacci(9);
	obj.odd_fibonacci(6);
	obj.odd_fibonacci(4);
	obj.odd_fibonacci(7);
	return 0;
}

 2-th Odd fibonacci element is : 1
 9-th Odd fibonacci element is : 233
 6-th Odd fibonacci element is : 21
 4-th Odd fibonacci element is : 5
 7-th Odd fibonacci element is : 55

//Include namespace system
using System;

// C# program 
// Find nth odd fibonacci number

class FibonacciNo
{
	//Find the nth odd element in fibonacci series
	public void odd_fibonacci(int n_th)
	{
		if (n_th <= 0)
		{
			return;
		}
		//Get location of nth odd element in fibonacci series
		int n = (3 * n_th + 1) / 2;
		//Define resultant variable
		int result = 0;
		int a = 0;
		int b = 1;
		//Find nth element in fibonacci serie
		for (int i = 1; i <= n; i++)
		{
			result = a;
			b = b + a;
			a = b - a;
		}
		//Display the calculated result result
		Console.Write("\n " + n_th + "-th Odd fibonacci element is : " + result);
	}
	public static void Main(String[] args)
	{
		FibonacciNo obj = new FibonacciNo();
		//Test case
		obj.odd_fibonacci(2);
		obj.odd_fibonacci(9);
		obj.odd_fibonacci(6);
		obj.odd_fibonacci(4);
		obj.odd_fibonacci(7);
	}
}

 2-th Odd fibonacci element is : 1
 9-th Odd fibonacci element is : 233
 6-th Odd fibonacci element is : 21
 4-th Odd fibonacci element is : 5
 7-th Odd fibonacci element is : 55

<?php
// Php program 
// Find nth odd fibonacci number

class FibonacciNo
{
	//Find the nth odd element in fibonacci series
	public	function odd_fibonacci($n_th)
	{
		if ($n_th <= 0)
		{
			return;
		}
		//Get location of nth odd element in fibonacci series
		$n = intval((3 * $n_th + 1) / 2);
		//Define resultant variable
		$result = 0;
		$a = 0;
		$b = 1;
		//Find nth element in fibonacci serie
		for ($i = 1; $i <= $n; $i++)
		{
			$result = $a;
			$b = $b + $a;
			$a = $b - $a;
		}
		//Display the calculated result result
		echo "\n ". $n_th ."-th Odd fibonacci element is : ". $result;
	}
}

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

 2-th Odd fibonacci element is : 1
 9-th Odd fibonacci element is : 233
 6-th Odd fibonacci element is : 21
 4-th Odd fibonacci element is : 5
 7-th Odd fibonacci element is : 55

// Node Js program 
// Find nth odd fibonacci number
class FibonacciNo
{
	//Find the nth odd element in fibonacci series
	odd_fibonacci(n_th)
	{
		if (n_th <= 0)
		{
			return;
		}
		//Get location of nth odd element in fibonacci series
		var n = parseInt((3 * n_th + 1) / 2);
		//Define resultant variable
		var result = 0;
		var a = 0;
		var b = 1;
		//Find nth element in fibonacci serie
		for (var i = 1; i <= n; i++)
		{
			result = a;
			b = b + a;
			a = b - a;
		}
		//Display the calculated result result
		process.stdout.write("\n " + n_th + "-th Odd fibonacci element is : " + result);
	}
}

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

 2-th Odd fibonacci element is : 1
 9-th Odd fibonacci element is : 233
 6-th Odd fibonacci element is : 21
 4-th Odd fibonacci element is : 5
 7-th Odd fibonacci element is : 55

#  Python 3 program 
#  Find nth odd fibonacci number

class FibonacciNo :
	# Find the nth odd element in fibonacci series
	def odd_fibonacci(self, n_th) :
		if (n_th <= 0) :
			return
		
		# Get location of nth odd element in fibonacci series
		n = int((3 * n_th + 1) / 2)
		# Define resultant variable
		result = 0
		a = 0
		b = 1
		i = 1
		# Find nth element in fibonacci serie
		while (i <= n) :
			result = a
			b = b + a
			a = b - a
			i += 1
		
		# Display the calculated result result
		print("\n ", n_th ,"-th Odd fibonacci element is : ", result, end = "")
	

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

if __name__ == "__main__": main()

  2 -th Odd fibonacci element is :  1
  9 -th Odd fibonacci element is :  233
  6 -th Odd fibonacci element is :  21
  4 -th Odd fibonacci element is :  5
  7 -th Odd fibonacci element is :  55

#  Ruby program 
#  Find nth odd fibonacci number

class FibonacciNo 
	# Find the nth odd element in fibonacci series
	def odd_fibonacci(n_th) 
		if (n_th <= 0) 
			return
		end

		# Get location of nth odd element in fibonacci series
		n = (3 * n_th + 1) / 2
		# Define resultant variable
		result = 0
		a = 0
		b = 1
		i = 1
		# Find nth element in fibonacci serie
		while (i <= n) 
			result = a
			b = b + a
			a = b - a
			i += 1
		end

		# Display the calculated result result
		print("\n ", n_th ,"-th Odd fibonacci element is : ", result)
	end

end

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

main()

 2-th Odd fibonacci element is : 1
 9-th Odd fibonacci element is : 233
 6-th Odd fibonacci element is : 21
 4-th Odd fibonacci element is : 5
 7-th Odd fibonacci element is : 55

// Scala program 
// Find nth odd fibonacci number
class FibonacciNo
{
	//Find the nth odd element in fibonacci series
	def odd_fibonacci(n_th: Int): Unit = {
		if (n_th <= 0)
		{
			return;
		}
		//Get location of nth odd element in fibonacci series
		var n: Int = ((3 * n_th + 1) / 2).toInt;
		//Define resultant variable
		var result: Int = 0;
		var a: Int = 0;
		var b: Int = 1;
		var i: Int = 1;
		//Find nth element in fibonacci serie
		while (i <= n)
		{
			result = a;
			b = b + a;
			a = b - a;
			i += 1;
		}
		//Display the calculated result result
		print("\n " + n_th + "-th Odd fibonacci element is : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: FibonacciNo = new FibonacciNo();
		//Test case
		obj.odd_fibonacci(2);
		obj.odd_fibonacci(9);
		obj.odd_fibonacci(6);
		obj.odd_fibonacci(4);
		obj.odd_fibonacci(7);
	}
}

 2-th Odd fibonacci element is : 1
 9-th Odd fibonacci element is : 233
 6-th Odd fibonacci element is : 21
 4-th Odd fibonacci element is : 5
 7-th Odd fibonacci element is : 55

// Swift 4 program 
// Find nth odd fibonacci number
class FibonacciNo
{
	//Find the nth odd element in fibonacci series
	func odd_fibonacci(_ n_th: Int)
	{
		if (n_th <= 0)
		{
			return;
		}
		//Get location of nth odd element in fibonacci series
		let n: Int = (3 * n_th + 1) / 2;
		//Define resultant variable
		var result: Int = 0;
		var a: Int = 0;
		var b: Int = 1;
		var i: Int = 1;
		//Find nth element in fibonacci serie
		while (i <= n)
		{
			result = a;
			b = b + a;
			a = b - a;
			i += 1;
		}
		//Display the calculated result result
		print("\n ", n_th ,"-th Odd fibonacci element is : ", result, terminator: "");
	}
}
func main()
{
	let obj: FibonacciNo = FibonacciNo();
	//Test case
	obj.odd_fibonacci(2);
	obj.odd_fibonacci(9);
	obj.odd_fibonacci(6);
	obj.odd_fibonacci(4);
	obj.odd_fibonacci(7);
}
main();

  2 -th Odd fibonacci element is :  1
  9 -th Odd fibonacci element is :  233
  6 -th Odd fibonacci element is :  21
  4 -th Odd fibonacci element is :  5
  7 -th Odd fibonacci element is :  55

Resultant Output Explanation

Let's take a look at the outputs from the provided code:

1. The 2nd odd Fibonacci element is 1.
2. The 9th odd Fibonacci element is 233.
3. The 6th odd Fibonacci element is 21.
4. The 4th odd Fibonacci element is 5.
5. The 7th odd Fibonacci element is 55.

Time Complexity of the Code

The time complexity of the given code is O(n), where n is the location of the Nth odd element in the Fibonacci series. The loop iterates 'n' times to find the Fibonacci number at the 'n-th' position, making it linear in terms of the input 'n'. Since the rest of the operations in the code are constant time, they do not significantly affect the overall time complexity.