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
- Start
- Input the value of N (the position of the odd Fibonacci element to be found)
- If N is less than or equal to 0, return
- Calculate the location of the Nth odd element: n = (3 * N + 1) / 2
- Initialize variables: result = 0, a = 0, b = 1
- Loop i from 1 to n a. Set result = a b. Set b = b + a c. Set a = b - a
- Print the N-th Odd Fibonacci element: result
- End
Algorithm Explanation
- We first check if N is valid (greater than 0) and if not, we return since there's no valid output for invalid N.
- 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.
- We then initialize variables a and b to 0 and 1, respectively, to start the Fibonacci sequence.
- We loop from 1 to n, updating a and b in each iteration to calculate the Nth element in the Fibonacci series.
- After the loop, the value of 'result' will be the Nth element in the Odd Fibonacci series.
- Finally, we print the result as the Nth odd element.
Code Solution
Here given code implementation process.
// 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;
}
Output
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);
}
}
Output
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;
}
Output
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);
}
}
Output
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();
Output
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();
Output
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()
Output
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()
Output
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);
}
}
Output
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();
Output
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:
- The 2nd odd Fibonacci element is 1.
- The 9th odd Fibonacci element is 233.
- The 6th odd Fibonacci element is 21.
- The 4th odd Fibonacci element is 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.
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