O(log n) approach


#1

void multiply(int mat[2][2],int m[2][2]){
int temp[2][2];
temp[0][0]=mat[0][0]*m[0][0]+mat[0][1]*m[1][0];
temp[0][1]=mat[0][0]*m[0][1]+mat[0][1]*m[1][1];
temp[1][0]=mat[1][0]*m[0][0]+mat[1][1]*m[1][0];
temp[1][1]=mat[1][0]*m[0][1]+mat[1][1]*m[1][1];
mat[0][0]=temp[0][0];
mat[0][1]=temp[0][1];
mat[1][0]=temp[1][0];
mat[1][1]=temp[1][1];

}
void mat_power(int mat[2][2],int n){
if(n==1) return;
mat_power(mat,n/2);
multiply(mat,mat);
int m[2][2]={
{1,1},
{1,0}
};
if(n%2!=0) multiply(mat,m);

}
int Solution::climbStairs(int A) {
if(A<=2) return A;
int n=A+1;
int mat[2][2]={
{1,1},
{1,0}
};
mat_power(mat,n);
return mat[0][1];

}


#2

Could you please explain the solution? It is not very clear from just the code.
Thanks in advance.


#3