About the Series
Problem-solving is a key skill set for any tech-related stuff you might be working on.
When it comes to developers it's one of the most crucial skills which is needed in almost any day-to-day code you might be writing.
So, this series of blogs is all about practicing Daily LeetCode Challenges & Problem-solving. 🚀
Problem Statement
Fibonacci Number
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) = 1F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
Example 1:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
Video Explanation
Solution 1: Recursive Approach
Algorithm
- This is the recursive solution where If
n is 0 it will return 0 or if n is 1 it will return 1. This is the base case for recursion
- Recursively call the
f(n-1) and f(n-2) to return the final value of f(n)
- Finally we get out
f(n).
Code in JS 🧑💻
var fib = function (n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
};
Time Complexity : O(n)
Space Complexity: O(n)
Solution 2: Iterative approach with an array
Algorithm
- First of all,
n = 0 return 0 and for n = 1 return 1
- Create an array and store the first two values of the Fibonacci sequence in the array
- Now update the
ith value of the array with the i-1 value + the i-2 value of the array.
- Repeat the same for n iterations and then the array will have the
nth value too.
- Return the
nth value from the array
Code in JS 🧑💻
var fib = function (n) {
if (n < 2) return n;
var fibArray = [];
fibArray[0] = 0;
fibArray[1] = 1;
for (var i = 2; i <= n; i++) {
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
return fibArray[n];
};
Time Complexity : O(n)
Space Complexity: O(n)
Solution 3: Iterative approach without an array
Algorithm
The approach is similar to the 2nd solution but it is done without using a new array.
- First of all,
n = 0 return 0 and for n = 1 return 1
- Store the last two values of the Fibonacci series in
f1 and f2.
- Update
f1 with f2
- Update
f2 with the current sum of f1 and f2.
- Steps 2 and 3 will be repeated till we get the final value after n iterations.
- Return
f2.
Code in JS 🧑💻
var fib = function (n) {
if (n < 2) return n;
var f1 = 0;
var f2 = 1;
for (var i = 2; i <=n; i++) {
var currentSum = f1 + f2;
f1 = f2;
f2 = currentSum;
}
return f2;
};
Time Complexity : O(n)
Space Complexity: O(1)
Similar Questions for practice
Now it is time to try some similar questions
You can find me on the web 🌍
Add your solution or approach in the comments below. Also, show your love by Sharing the blog. 🤗
“Belief creates the actual fact.”
~ William James
