O(log(n)) integer-only solution in 6 lines. Python rocks!


  • -2
    T

    Matrix multiplication method, fat free.

    def climbStairs(self, n):
        a,b,x,y = 1,1,1,0
        while n>0:
            if n&1: x, y = a*x + b*y, b*x + y*(a-b)
            a,b,n = a*a + b*b, 2*a*b - b*b, n>>1;
        return x;

Log in to reply
 

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