All suggestions are welcome. Please upvote if you like it. Thank you.
Leetcode Problem Link: 509. Fibonacci Number
Brute Force Solution:
For n=5, there are (2^(n-1))-1=15 recursive calls which leads to Time O(2^N) & Auxiliary Space O(1)
class Solution {
public:
int fib(int n) {
// Brute Force Solution
if(n==0 || n==1){
return n;
}
return fib(n-1) + fib(n-2);
}
};
Efficient Solution(Dynamic Programming Bottom Up Approach):
Using sum vector to store intermediate fibonacci numbers computed in order to avoid redundant calculations. Time O(N) & Auxiliary Space O(N)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target){
//Efficient Solution TimeO(N) & Auxiliary Space O(N)
int length=nums.size();
unordered_map<int,int> map;
for(auto i=0;i<length;i++){
if(map.find(target-nums[i])!=map.end()){
return {i,map[target-nums[i]]};
}
map[nums[i]]=i;
}
return {};
}
};
Efficient Solution(Dynamic Programming Bottom Up Approach(Storing the two most recent intermediate fibonacci numbers calculated):
Time O(N) & Auxiliary Space O(1)
class Solution {
public:
int fib(int n) {
// Efficient Solution
if(n==0 || n==1){
return n;
}
int f_minus_1 = 0, f = 1;
for(int i = 2; i <= n; i++){
f = f + f_minus_1;
f_minus_1 = f - f_minus_1;
}
return f;
}
};
Efficient Solution(Matrix Multiplication & Binary Exponentiation):
Time is O(logN) & Auxiliary Space O(logN) due to recursive stack calls in power() function
// Matrix mulplication
/*
| fib(n) | |1 1| |fib(n-1)|
| | = | | * | |
|fib(n-1)| |1 0| |fib(n-2)|
For n=2,
|fib(2)| |1 1| |fib(1)|
| | = | | * | |
|fib(1)| |1 0| |fib(0)|
For n=3,
|fib(3)| |1 1|^2 |fib(1)|
| | = | | * | |
|fib(2)| |1 0| |fib(0)|
General Expression :
| fib(n) | |1 1|^(n-1) |fib(1)=1|
| | = | | * | |
|fib(n-1)| |1 0| |fib(0)=0|
*/
class Solution {
public:
void mul(int A[2][2], int B[2][2])
{
// Multiplying 2x2 matrices in time O(1)
int A00 = (A[0][0] * B[0][0]) + (A[0][1] * B[1][0]);
int A01 = (A[0][0] * B[0][1]) + (A[0][1] * B[1][1]);
int A10 = (A[1][0] * B[0][0]) + (A[1][1] * B[1][0]);
int A11 = (A[1][0] * B[0][1]) + (A[1][1] * B[1][1]);
A[0][0] = A00; A[0][1] = A01; A[1][0] = A10; A[1][1] = A11;
}
void power(int A[2][2], int exp)
{
// Calculates matrix multiplication using binary exponentiation in time O(logN)
// A^x=A^(x/2) * A^(x/2), if x is even
// A^x=A * A^(x/2) * A^(x/2), if x is odd
int B[2][2] = { {1,1} , {1,0} };
if(exp == 0 || exp == 1)
return;
power(A, exp/2);
mul(A, A);
if(exp%2!=0)
mul(A, B);
}
int fib(int n)
{
// Efficient Solution
int A[2][2] = { {1,1} , {1,0} };
if(n == 0)
return 0;
power(A, n-1);
// A[0][0] is the required nth fibonacci number
return A[0][0];
}
};
Optimal Solution(Binet's Formula):
Time O(1) & Auxiliary Space O(1)
class Solution {
public:
int fib(int n) {
// Optimal Solution
// The formula is true for all n but works till n=70 in C++ implementation
// due to approximations in computations & range limits of data types.
// Double data type ensures high precision and correct answer till n=70
double z = sqrt(5);
double t = (pow(2,n)*z);
double a = (pow(1+z,n));
double b = (pow(1-z,n));
cout<<fixed; // Converts scientific notation to fixed-point notation
cout<<round((a-b)/t); // Rounds off the decimals and replaces them with 0's
}
};
All suggestions are welcome. Please upvote if you like it. Thank you.
Top comments (0)