Fibonacci O(log(n))

 avatar
unknown
python
19 days ago
910 B
4
Indexable
class Solution {
public:
    int climbStairs(int n) {
        int currentVector [2][2] = {{1, 1}, {1, 0}};
        int finalVector [2] = {1, n & 0x1};
        for (n >>= 1; n; n >>= 1) {
            square(currentVector);
            if (n & 0x1) dotInPlaceOfB(currentVector, finalVector);
        }
        return finalVector[0];
    }

    # Note: use numpy array libraries like np.dot and np.matmul to further simplify
    void dotInPlaceOfB(int (&a)[2][2], int (&b) [2]) {
        int b0 = b[0], b1 = b[1];
        b[0] = a[0][0] * b0 + a[0][1] * b1;
        b[1] = a[1][0] * b0 + a[1][1] * b1;
    }

    void square(int (&a) [2][2]) {
        int a00 = a[0][0], a01 = a[0][1], a10 = a[1][0], a11 = a[1][1];
        a[0][0] = a00 * a00 + a01 * a10;
        a[0][1] = a00 * a01 + a01 * a11;
        a[1][0] = a10 * a00 + a11 * a10;
        a[1][1] = a10 * a01 + a11 * a11;
    }
}
Editor is loading...
Leave a Comment