Count Ways To Reach The N-th Stairs
You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair. Each time you can either climb one step or two steps. You are supposed to return the number of distinct ways in which you can climb from the 0th step to Nth step.

Example :

N=3

We can climb one step at a time i.e. {(0, 1) ,(1, 2),(2,3)} or we can climb the first two-step and then one step i.e. {(0,2),(1, 3)} or we can climb first one step and then two step i.e. {(0,1), (1,3)}.

Input format :

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow. The first and the only argument of each test case contains an integer 'N', representing the number of stairs.

Output format :

For each test case/query, print the number of distinct ways to reach the top of stairs. Since the number can be huge, so return output modulo 10^9+7. Output for every test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of.

Constraints :

1

Question

Count Ways To Reach The N-th Stairs

You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair. Each time you can either climb one step or two steps. You are supposed to return the number of distinct ways in which you can climb from the 0th step to Nth step.

Example :

N=3

Example

We can climb one step at a time i.e. {(0, 1) ,(1, 2),(2,3)} or we can climb the first two-step and then one step i.e. {(0,2),(1, 3)} or we can climb first one step and then two step i.e. {(0,1), (1,3)}.

Input format :

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow.

The first and the only argument of each test case contains an integer 'N', representing the number of stairs.

Output format :

For each test case/query, print the number of distinct ways to reach the top of stairs. Since the number can be huge, so return output modulo 10^9+7.

Output for every test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of.

Constraints :

1 <= T <= 100
0 <= N <= 10^18

Where 'T' is the number of test cases, and 'N' is the number of stairs.

Accepted Answer

Brute Force

One basic approach is to explore all possible steps which can be climbed with either taking one step or two steps. So at every step, we have two options to climb the stairs either we can climb with one step, or we can climb with two steps. So the number of ways can be recursively defined as :

countDistinctWayToClimbStair ( currStep, N ) = countDistinctWayToClimbStair ( currStep+1, N ) + countDistinctWayToClimbStair ( currStep + 2, N )

Where “currStep” denotes the current step on which the person is standing, and N denotes the destination step.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of stairs.

In the worst-case scenario, when we climb one step each time, then the depth of the recursion tree will be ‘N’. So space complexity will be O(N).

Time Complexity: O(2^n)Explanation:

O(2^N), Where ‘N’ is the number of stairs.

There will be ‘N’ steps to climb, and at every step, we have two options to climb. So there will be 2^N ways to climb ‘N’ stairs which is the size of the recursion tree.

Recursion tree for N=5 would be like this :

Accepted Answer

Using Memoization

In the previous approach, we were naively calculating the results for every step. So there were lots of redundant calls because if we look at the recursion tree, then there are only ‘N’ distinct function calls. So we should avoid redundant function calling. For that, we decide to store the result at each step, and we will directly return the result for that step whenever a function is called again for those steps. We will be storing the result into “dp”.

Where dp[currStep] defines the number of distinct ways to climb the stairs from “currStep” to ‘N’-th steps.

Note :

Since N can be 10^18 so even if you will be creating the array of integers then also it'll give the memory limit to exceed.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of stairs.

We are storing the result of every step in the dp array of size N. So there will be ‘N’ steps, And also we are using recursion to explore all the possible steps. So in the worst-case scenario, when we climb one step each time, then the depth of the recursion tree will be ‘N’. So space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of stairs.

Since there will be only ‘N’ distinct function calls because we are saving the result at every step so there will be no redundant function calls, so overall time complexity will be O(N).

Accepted Answer

Using Dynamic Programming

As we have seen that this problem can be broken into subproblems. And many subproblems were the same, so for that; we were using memoization. So instead of storing the result through recursion, we are going to store the result iteratively. Our intuition is:

How can we reach “currStep” step in taking one step or two steps:

We can take the one-step from (currStep-1)th step or,
We can take the two steps from (currStep-2)th step.

So the total number of ways to reach “currStep” will be the sum of the total number of ways to reach at (currStep-1)th and the total number of ways to reach (currStep-2)th step.

Let dp[currStep] define the total number of ways to reach “currStep” from the 0th. So,

dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]

The base case will be, If we have 0 stairs to climb then the number of distinct ways to climb will be one (we are already at Nth stair that’s the way) and if we have only one stair to climb then the number of distinct ways to climb will be one, i.e. one step from the beginning.

Note :

Since N can be 10^18 so even if you will be creating the array of integers then also it'll give the memory limit to exceed.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of stairs.

Since we are storing the result into “dp” for every step, there will be ‘N’ steps. So space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of stairs.

We are traversing in “dp” only once to fill the”dp”. So time complexity will be O(N).

Accepted Answer

Matrix multiplication

In the previous approach, we were using “dp” which took O(N) space. But there was no need of taking a space of O(N). Because if we look at any step of dp:

     dp[ currStep ] = dp[ currStep-1 ] + dp[ currStep-2 ]

We only need the answer of the two-step and the one-step before the “currStep” for evaluation of the “currStep”. So we can replace “dp” with two variables let’s say “oneStep” and “twoSteps”. Where “oneStep” denotes the total number of ways to reach (currStep-1)th step from beginning and “twoSteps” denotes the total number of ways to reach (currStep-2)th step from the beginning. So,

         currStep=oneStep+twoStep

So the above statement is (N-1)th Fibonacci Number. We can calculate the ‘N’th Fibonacci Number using Binary Matrix Exponentiation explained below. Here, Fn represents the nth Fibonacci number. We will raise the matrix to the power of (n - 1) so that the top-left element gives the value of F(n + 1 - 1) = F(n).

[[1 1] (pow n) [[(F(n+1) F(n)]

[1 0]] = [ F(n) F(n-1)]]

So we need to find the (N - 1)th Power of this Matrix.
We can write a function for the multiplication of two matrices.
Then we can use binary exponentiation to calculate the ‘N’ power of this Matrix in log(N).
Binary Exponentiation / Fast Exponentiation:

long long binpow(Matrix a, long long b) {
if (b == 0)
     return 1;
Matrix res = binpow(a, b / 2);
if (b % 2)
     return res * res * a;
else
     return res * res;
}

Similarly, we can write a version for Matrix Exponentiation.
Take care of overflow using modulo by 10^9 + 7 at each operation of Matrix Multiplication.

Space Complexity: O(logn)Explanation:

O(log(N)),

Recursion stack takes O(log N) space. So Overall space complexity is O(log N).

Time Complexity: O(logn)Explanation:

O(log(N)), where N is the number of stairs.

As we are diving N by 2 till it becomes 0, so that’s log(N) times multiplication of 2*2 Matrix. So Overall Time Complexity is O(log(N)).

You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair. Each time you can either climb one step or two steps. You are supposed to return the number of distinct ways in which you can climb from the 0th step to Nth step.

Example :

Input format :

Output format :

Note :

Constraints :

Top DXC Technology Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in DXC Technology Software Developer