VietMX Staff asked 4 years ago
The algorithm is based on this innocent-looking identity (which can be proven by mathematical induction):
Complexity Analysis
- Time complexity :
O(log n). By halving the N value in every matrixPower’s call to itself, we are halving the work needed to be done. - Space complexity :
O(log n). The size of the stack in memory is proportionate to the function calls to matrixPower plus the memory used to account for the matrices which takes up constant space.
Implementation
class Solution { int fib(int N) { if (N <= 1) { return N; } int[][] A = new int[][]{{1, 1}, {1, 0}}; matrixPower(A, N-1); return A[0][0]; } void matrixPower(int[][] A, int N) { if (N <= 1) { return; } matrixPower(A, N/2); multiply(A, A); int[][] B = new int[][]{{1, 1}, {1, 0}}; if (N%2 != 0) { multiply(A, B); } } void multiply(int[][] A, int[][] B) { int x = A[0][0] * B[0][0] + A[0][1] * B[1][0]; int y = A[0][0] * B[0][1] + A[0][1] * B[1][1]; int z = A[1][0] * B[0][0] + A[1][1] * B[1][0]; int w = A[1][0] * B[0][1] + A[1][1] * B[1][1]; A[0][0] = x; A[0][1] = y; A[1][0] = z; A[1][1] = w; }}