LeetCode Question - 509. Fibonacci Number π€ͺ
6th July 2022 | π Daily LeetCode Challenge - #6
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
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).
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
is0
it will return0
or ifn
is1
it will return1
. This is the base case for recursion - Recursively call the
f(n-1)
andf(n-2)
to return the final value off(n)
- Finally we get out
f(n)
.
Code in JS π§βπ»
/**
* @param {number} n
* @return {number}
*/
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
return0
and forn = 1
return1
- 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 thei-1
value + thei-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 π§βπ»
/**
* @param {number} n
* @return {number}
*/
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
return0
and forn = 1
return1
- Store the last two values of the Fibonacci series in
f1
andf2
. - Update
f1
withf2
- Update
f2
with the current sum off1
andf2
. - Steps 2 and 3 will be repeated till we get the final value after n iterations.
- Return
f2
.
Code in JS π§βπ»
/**
* @param {number} n
* @return {number}
*/
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
- Climbing Stairs
- Split Array into Fibonacci Sequence
- Length of Longest Fibonacci Subsequence
- N-th Tribonacci Number
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