Fibonacci Numbers

Fibonacci Numbers are

Fibonacci numbers are generated using the following recurrence relation

It is interesting to note that the Fibonacci number grows so fast that exceeds the 32-bit signed integer range.

The fastest way to accurately compute Fibonacci numbers is by using a matrix-exponentiation method.

We need to calculate to calculate the Nth fibonacci number. We can calculate it in using fast exponentiation.

Simple Recursive Solution

fibonacci(n)
    if(n=0)
        return 0
    if (n=1)
        return 1
    return (fibonacci(n-1)+fibonacci(n-2))

Time complexity:

Optimization using Dynamic Programming

There are only n overlapping subproblems which can be stored to reduce the time complexity to

//Initialize all elements in dp to -1
fibonacci(n)
    if(dp[n]!=-1)
        return dp[n]
    if(n=0)
        dp[n]=0
    else if (n=1)
        dp[n]=1
    else
        dp[n]=fibonacci(n-1)+fibonacci(n-2)  
    return dp[n]

Time Complexity =
Space Complexity =

Using Matrix Exponentiation

//Calculating A^p in O(log(P))
Matrix_pow ( Matrix A,int p )
    if(p=1)
        return A
    if(p%2=1)
        return A*Matrix_pow(A,p-1)  

    Matrix B = Matrix_pow(a,p/2);
    return B * B

fibonacci(n)
    if(n=0)
        return 0;
    if(n=1)
        return 1;
    Matrix M[2][2]={{1,1},{1,0}}
    Matrix res=matrix_pow(M,n-1);
    return res[0][0];

Time Complexity =

 
Related challenge for Fibonacci Numbers
Go to Top
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score