509. Fibonacci Number [Leetcode][C++]

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.

Blog

509. Fibonacci Number [Leetcode][C++]

Mayank Arora

Join Our Newsletter. No Spam, Only the good stuff.

Related