Fibonacci O(log(n))
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