O(log(n)) solution with matrix multiplication


  • 6
    T

    I saw most solutions posted in discussion are DP with runtime O(n) and O(1) space which is accepted by OJ.

    The only O(log(n)) solution so far is lucastan's using Binet's formula.

    There actually is a matrix multiplication solution which also runs in O(log(n)). It basically calculates fibonacci numbers by power of matrix ((0, 1), (1, 1)) ^ (n-1).

        public int climbStairs1(int n) {
        int[][] a = {{0, 1}, {1, 1}};
        int[][] m = pow(a, n - 1);
        return m[0][1] + m[1][1];
    }
    
    private int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    
    private int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }

  • 2
    T

    In fact there is no need to store (and calculate) full (2x2) matrix. Matrix looks like this:

    F(n+1)  F(n)
    F(n)    F(n-1)
    

    We know that F(n-1) = F(n+1) - F(n), so all we need is just 2 numbers.

    Here's my (prety cryptic) solution based on optimized matrix multiplication.

    class Solution {
    public:
        int climbStairs(int n) {
           // {x,y} is result matrix, {a,b} is pow-2 matrix, t is to store temporary values
            int x=1, y=0, a=1, b=1, t; 
               
            while (n>0) {
                
                if (n&1) { 
                    // {x,y} * {a,b}
    
                    t = b*x;
                    x = a*x + b*y;
                    y = t + y*(a-b);
                }
                
               // {a,b}^2
    
                t = 2*a-b;
                a = a*a + b*b;
                b *= t;
                
                n >>= 1;
            }   
            return x;
        }
    };
    

Log in to reply
 

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