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 <= T <= 100 0 <= N <= 10^18 Where 'T' is the number of test cases, and 'N' is the number of stairs.

Approach (Using DP) : 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. TC : O(N), where N = number of stairs. SC : O(N)

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 :

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).

Asked inInfosys,System Engineer

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...

CodingNinjas

author

Approach (Using DP) : 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...

CodingNinjas

author

Brute ForceOne 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 cl...

CodingNinjas

author

Using MemoizationIn 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 ‘...

Add answer anonymously...

Top Infosys System Engineer interview questions & answers

Popular interview questions of System Engineer

Top HR questions asked in Infosys System Engineer