Program to find Nth odd Fibonacci Number
Given an integer N. The task is to find the Nth odd Fibonacci number.
The odd number fibonacci series is as:
1, 1, 3, 5, 13, 21, 55, 89, 233, 377, 987, 1597………….and so on.
Note: In the above series we have omitted even terms from the general fibonacci sequence.
Examples:
Input: N = 3 Output: 3 Input: N = 4 Output: 5
Approach:
On observing carefully, it can be deduced that every third Fibonacci number is even, so the Nth odd Fibonacci number is the {(3*N+1)/2}th term in the general Fibonacci sequence.
Below is the implementation of the above approach:
C++
// C++ program for Nth odd fibonacci number #include <bits/stdc++.h> using namespace std; // Function to find nth odd fibonacci number int oddFib( int n) { n = (3 * n + 1) / 2; int a = -1, b = 1, c, i; for (i = 1; i <= n; i++) { c = a + b; a = b; b = c; } return c; } // Driver Code int main() { int n = 4; cout << oddFib(n); return 0; } |
Java
// Java program for Nth odd fibonacci number class GFG { // Function to find nth odd fibonacci number static int oddFib( int n) { n = ( 3 * n + 1 ) / 2 ; int a = - 1 , b = 1 , c = 0 , i; for (i = 1 ; i <= n; i++) { c = a + b; a = b; b = c; } return c; } // Driver Code public static void main (String[] args) { int n = 4 ; System.out.println(oddFib(n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 program for Nth odd fibonacci number # Function to find nth odd fibonacci number def oddFib(n): n = ( 3 * n + 1 ) / / 2 a = - 1 b = 1 c = 0 for i in range ( 1 , n + 1 ): c = a + b a = b b = c return c # Driver Code n = 4 print (oddFib(n)) # This code is contributed by mohit kumar |
C#
// C# program for Nth odd fibonacci number using System; class GFG { // Function to find nth odd fibonacci number static int oddFib( int n) { n = (3 * n + 1) / 2; int a = -1, b = 1, c = 0, i; for (i = 1; i <= n; i++) { c = a + b; a = b; b = c; } return c; } // Driver Code public static void Main (String[] args) { int n = 4; Console.WriteLine(oddFib(n)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for Nth odd fibonacci number // Function to find nth odd fibonacci number function oddFib(n) { n = (3 * n + 1) / 2; var a = -1, b = 1, c, i; for (i = 1; i <= n; i++) { c = a + b; a = b; b = c; } return c; } // Driver Code var n = 4; document.write(oddFib(n)); </script> |
Output:
5
Time Complexity: O(N)
Auxiliary Space: O(1)