Short Problem Definition:
Count the number of different ways of climbing to the top of a ladder.
expected worst-case time complexity is O(L)
expected worst-case space complexity is O(L)
We first compute the Fibonacci sequence for the first L+2 numbers. The first two numbers are used only as fillers, so we have to index the sequence as A[idx]+1 instead of A[idx]-1. The second step is to replace the modulo operation by removing all but the n lowest bits. A discussion can be found on Stack Overflow.
def solution(A, B): L = max(A) P_max = max(B) fib =  * (L+2) fib = 1 for i in xrange(2, L + 2): fib[i] = (fib[i-1] + fib[i-2]) & ((1 << P_max) - 1) return_arr =  * len(A) for idx in xrange(len(A)): return_arr[idx] = fib[A[idx]+1] & ((1 << B[idx]) - 1) return return_arr
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.