PROBLEM LINK:
Author: Manas Rawat
Tester: Aagam Jain
Editorialist: Manas Rawat
DIFFICULTY:
EASY - MEDIUM
PROBLEM:
If we look closely at the question statement then the number of ways to reach a step depends on the number of ways to reach the previous two steps. So this forms a fibonacci series. We just have to find the Nth fibonacci number in this question.
QUICK EXPLANATION:
Finding the Nth Fibonacci Number is easy but the contraints in this question does not allow us to do so easily. We can use our knowledge on Recurrence Relation and Matrix Exponentiation to find out the answer in log(N) time. If you don’t know about Recurrence Relation then you can watch this video by CodeNCode where he has eplained the same.
SOLUTIONS:
Solution can be found here.