My C solution,0ms,O(log n),use matrix and quick pow


  • 0
    A
    int climbStairs(int n) {
    	// ([1 1,1 0]^n)[0][0]
    	int r[2][2]={{1,0},{0,1}},
    		x[2][2]={{1,1},{1,0}},
    		t[2][2];
    	while(n) {
    		if(n&1) {
    			memcpy(&t,&r,sizeof t);
    			// r=t*x
    			r[0][0]=t[0][0]*x[0][0]+t[0][1]*x[1][0];
    			r[0][1]=t[0][0]*x[0][1]+t[0][1]*x[1][1];
    			r[1][0]=t[1][0]*x[0][0]+t[1][1]*x[1][0];
    			r[1][1]=t[1][0]*x[0][1]+t[1][1]*x[1][1];
    		}
    		memcpy(&t,&x,sizeof t);
    		// x=t*t
    		x[0][0]=t[0][0]*t[0][0]+t[0][1]*t[1][0];
    		x[0][1]=t[0][0]*t[0][1]+t[0][1]*t[1][1];
    		x[1][0]=t[1][0]*t[0][0]+t[1][1]*t[1][0];
    		x[1][1]=t[1][0]*t[0][1]+t[1][1]*t[1][1];
    		n>>=1;
    	}
    	return r[0][0];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.