Attempt Question : https://www.codingninjas.com/codestudio/problems/nth-fibonacci-number_1115780?leftPanelTab=0
-------------------------------------------
Register for codekaze 2023 <Click Here> or use this link : https://bit.ly/42bokC6//Become Coding ninja entrprenuer
//Register Now at : https://bit.ly/3MC2rGg
-------------------------------------------
Solution to Coding Ninja Question
#include <bits/stdc++.h>
typedef vector<vector<long long>> Matrix;
const long long mod = 1e9 + 7;
Matrix mul(Matrix a,Matrix b){
Matrix res(2,vector<long long>(2,0));
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
res[i][j]+=((a[i][k]*b[k][j])%mod);
res[i][j]%= mod;
}
}
}
return res;
}
Matrix matrix_pow(Matrix coef,int n){
if(n==0){
return {{1,0},{0,1}};
}
Matrix res=matrix_pow(coef,n/2);
if(n%2)//odd
{
res=mul(res,res);
res=mul(res,coef);
}
else{
res=mul(res,res);
}
return res;
}
int fibonacciNumber(int n){
Matrix coef={{1,1},{1,0}};
Matrix res=matrix_pow(coef,n-1);
int result=(int)res[0][0];
return result;
}
//Become Coding ninja entrprenuer
//Register Now at : https://bit.ly/3MC2rGg
