We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The O(logN) algorithms explained there involve polynomial root (or eigenvalues) search and may be quite laborious if you don't have a powerful math library. Also, they involve floating point numbers. Alternatively you have the relatively straightforward matrix exponentation method, that is O(M^3 logN) which still works for us, and only uses integer numbers.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #114: Counting block combinations I
You are viewing a single comment's thread. Return to all comments →
Try to convert your recursion to matrix form using these ideas: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
The O(logN) algorithms explained there involve polynomial root (or eigenvalues) search and may be quite laborious if you don't have a powerful math library. Also, they involve floating point numbers. Alternatively you have the relatively straightforward matrix exponentation method, that is O(M^3 logN) which still works for us, and only uses integer numbers.