Fibonacci Number - Leetcode Solution

Problem Description:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. Given n, calculate F(n).

Solution:

The Fibonacci series can be solved using recursion or a iterative method. In both cases, we start by checking if the given input n is either 0 or 1. Because the Fibonacci sequence starts with 0 and 1, another base case will be when the input is either 0 or 1 that is the output will be the same as the input. This is because F(0) = 0 and F(1) = 1.

Recursive Method

In the recursive solution, we calculate the nth number in the sequence by adding the (n-1)th term and the (n-2)th term. We perform this operation until we get F(0) and F(1), which we know their values. The recursive function call continues until the base cases are reached, then it returns the sum to the previous call, which will then add its corresponding sum.

def fib(n): if n == 0: # Base case return 0 elif n == 1: # Base case return 1 else: return fib(n-1) + fib(n-2)

Iterative Method

In an iterative solution, we loop through from 0 to n, and at each iteration, we add the sum of the two previous values. The loop continues until we reach the nth number in the sequence. We use two variables to keep track of the previous numbers.

def fib(n): if n == 0: # Base case return 0 elif n == 1: # Base case return 1 else: prev_prev = 0 # F(0) prev = 1 # F(1) for _ in range(2,n+1): current = prev_prev + prev prev_prev = prev prev = current return current

Time and Space Complexity:

For the recursive implementation, the time complexity is O(2^n) and the space complexity is O(n). This is because the recursive function calls itself twice for each value of n.

For the iterative implementation, the time complexity is O(n) and the space complexity is O(1). This is because we only loop through the values of n, and keep track of two variables.You can use any of the two methods based on the requirements of the problem.

This problem is solved now!

1