Nth Fibonacci Number

Given a positive integer n, find the nth fibonacci number. Since the answer can be very large, return the answer modulo 1000000007.

Example 1:

Input: n = 2
Output: 1 
Explanation: 1 is the 2nd number
of fibonacci series.

Example 2:

Input: n = 5
Output: 5
Explanation: 5 is the 5th number
of fibonacci series.


Your Task:  
You dont need to read input or print anything. Complete the function nthFibonacci() which takes n as input parameter and returns nth fibonacci number.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1<= n <=1000

Solution :

We know that this can be solved using recursion and dp but what about the matrix. Lets start with a matrix [[a,b],[c,d]] and in the left we have [ f(n) , f(n-1) ] and in the right we have [[a,b],[c,d]]  multiplied by [ f(n-1) , f(n-2) ]. We can find the value of a,b,c, and d by matching their coefficients. so now we can find the Fibonacci by just multiplying the matrix n times. Just like we make our own power function to reduce the time to calculate the power of big numbers we will here use exponentiation to calculate the power of a matrix.

const int mod = 1e9+7;
    vector<vector<long long int>>st ={{1,1},{1,0}};
   
    vector<vector<long long int>> multiply(vector<vector<long long int>>&a,vector<vector<long long int>>&b){
        int n = a.size();
        vector<vector<long long int>>ans(n,vector<long long int>(n,0LL));
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                for(int k=0; k<n; k++){
                    ans[i][j] += (a[i][k]*b[k][j])%mod;
                }
                ans[i][j]%=mod;
            }
        }
        return ans;
    }
   
    vector<vector<long long int>> helper(vector<vector<long long int>>&a, int n){
        if(n==0)return {{1,0},{0,1}};
        if(n==1)return a;
        vector<vector<long long int>> temp = helper(a,n/2);
        vector<vector<long long int>> ans = multiply(temp,temp);
        if(n&1) ans = multiply(ans,a);
        return ans;
    }
   
 
    long long int nthFibonacci(long long int n){
        vector<vector<long long int>>ans = helper(st,n);
       
        return ans[0][1];
    }
const int mod = 1e9+7;
vector<vector<long long int>>st ={{1,1},{1,0}};
vector<vector<long long int>> multiply(vector<vector<long long int>>&a,vector<vector<long long int>>&b){
int n = a.size();
vector<vector<long long int>>ans(n,vector<long long int>(n,0LL));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<n; k++){
ans[i][j] += (a[i][k]*b[k][j])%mod;
}
ans[i][j]%=mod;
}
}
return ans;
}
vector<vector<long long int>> helper(vector<vector<long long int>>&a, int n){
if(n==0)return {{1,0},{0,1}};
if(n==1)return a;
vector<vector<long long int>> temp = helper(a,n/2);
vector<vector<long long int>> ans = multiply(temp,temp);
if(n&1) ans = multiply(ans,a);
return ans;
}
long long int nthFibonacci(long long int n){
vector<vector<long long int>>ans = helper(st,n);
return ans[0][1];
}
Made with ❤ by Raunit Verma Rate Us 5⭐ Here