Python Program to Find nth Fibonacci Number.

Given an integer 'n', write a Python program to print the nth Fibonacci number.

The nth Fibonacci number is defined as the sum of the (n-1)th and (n-2)th Fibonacci numbers, where the 0th and 1st Fibonacci numbers are 0 and 1, respectively.(alert-success)

Example:

Example 1:
Input: n = 6
Output: 8
Explanation: 0, 1, 1, 2, 5, 8
0+1 = 1
1+1 = 2
2+3 = 5
3+5 = 8

Example 2:
Input: 10
Output: 55

We can solve this problem using multiple approaches, let's discuss each of them one by one and understand which approach is best for us.

Find Fibonacci Number using Recursion.

Python code:

# function to print nth Fibonacci number
def fibonacci_recursive(n):
    if n == 0 or n == 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
# print value
print(fibonacci_recursive(10))

Output:

Time Complexity: O(2^n) - Exponential
Space Complexity: O(n) - Space required by the call stack of recursive calls

Find Fibonacci Number using Dynamic Programming.

In this approach, we use a list to store the Fibonacci numbers from 0 to n. We initialize the first two Fibonacci numbers (0 and 1) in the list, and then iterate over the remaining numbers from 2 to n, computing each Fibonacci number as the sum of the previous two numbers. Finally, we return the nth Fibonacci number from the list.

Python Code:

# Find Fibonacci number using Dynamic Programming
def fibonacci_dp(n):
    if n == 0 or n == 1:
        return n
    fib = [0, 1]
    for i in range(2, n+1):
        fib.append(fib[i-1] + fib[i-2])
    return fib[n]
# print output
print(fibonacci_dp(8))

Output:

Time Complexity: O(n) - Linear
Space Complexity: O(n) - Space required to store the list of Fibonacci numbers.

Fibonacci Number using Space-Optimized Dynamic Programming.

In this approach, we optimize the space complexity of the above dynamic programming approach by using only two variables to store the last two Fibonacci numbers.

We initialize variables to 0 and 1, and then iterate over the remaining numbers from 2 to n, computing each Fibonacci number as the sum of the previous two numbers. After each iteration, we update the two variables to store the last two Fibonacci numbers. Finally, we return the last value of the second variable, which is the nth Fibonacci number.

Python Code:

# find fibonacci num space-optimized DP solution
def fibonacci_optimized(n):
    if n == 0 or n == 1:
        return n
    a, b = 0, 1
    for i in range(2, n+1):
        c = a + b
        a, b = b, c
    return b
#print output
print(fibonacci_optimized(10))

Output:

Time Complexity: O(n) - Linear
Space Complexity: O(1) - Constant space required to store only two variables (a and b)

Read More:

Python Program to Reverse a Number.

Python Program to Check Prime Number.

Python Program to Find nth Fibonacci Number.

Find Fibonacci Number using Recursion.

Find Fibonacci Number using Dynamic Programming.

Fibonacci Number using Space-Optimized Dynamic Programming.

No comments:

Post a Comment