Home » Interview coding problems/challenges

# Find Total Ways to Reach Nth Stair from Bottom

Here, we are going to learn to find the solution to **find total ways to reach nth stair from bottom and its C++ implementation**.

Submitted by Divyansh Jaipuriyar, on August 18, 2020

**Problem statement:**

You are given a staircase, you need to find the total number of ways to reach the nth stair from the bottom of the staircase when you are only allowed to climb 1, 2 or 3 stairs at a time.

**Problem description:**

The problem needs you to find total possible ways through which we can reach our destination, we are allowed to take a stride of a maximum of 3 jumps from the current position. You are required to develop a certain algorithm that can find the total possible arrangement such that you can reach your destination in minimum possible time constraints.

**Input:**

The first test case of input is the *T* number of the test case, each test case consists of a single integer the *n*^{th} stair.

**Output:**

Print the number of ways to reach *n*^{th} stair from bottom in a new line for each test case.

**Examples:**

Input: T = 1 N = 4 Output: 7, total possible ways: 1+1+1+1 1+1+2 1+2+1 1+3 2+1 2+2 3+1

**Solution approach:**

**1) Recursive Approach:**

In this approach, we will make recursive calls each time until our base case reaches. We have the following base case:

if(n==0): then 1, as there is only one way to step on with n steps. if(n<0) then 0, as stair numbers cannot be negative.

Now each of the current stairs depends on the previous three stairs since we can take 1 2 or 3 step climb from the current step.

Therefore the overall recursion function *f(n)* becomes:

f(n)= 0,if(n<0) 1, if(n==0) f(n-1)+f(n-2)+f(n-3), otherwise.

**Time Complexity** for the above approach in the worst case is **exponential**.

**Space Complexity** for the above approach is the **liner**.

**2) Dynamic Programming Approach:**

**(a): Top Down Approach:**

In this approach we will use memorization technique, we create a *dp[]* state which are initially filled with -1, each time we calculate the state we fill the *dp[]* state, and each time we make recursive call we first check if the value is already calculated or not, if calculate then directly return it without calculating it again and again.

**(b) Bottom Up Approach:**

In this approach we will fill the *dp[]* state in bottom up manner in the following manner.

dp[0]=1; dp[1]=dp[2]=dp[3]=1 for other state: dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

**Time Complexity** for the above approach in the worst case is : **O(n)**

**Space Complexity** for the above approach in the worst case is: **O(n)**

**C++ Implementation (Recursive Approach):**

#include <bits/stdc++.h> using namespace std; typedef long long ll; //solve function which will return //total ways for nth stair. ll solve(ll n) { //base case if we are at bottom. if (n == 0) return 1; //base case if negative stair is //encountered. if (n < 0) return 0; else //other cases as nth stair depends //previous three stairs as well. return solve(n - 1) + solve(n - 2) + solve(n - 3); } int main() { cout << "Enter number of test cases: "; ll t; cin >> t; while (t--) { cout << "Enter Nth stair: "; ll n; cin >> n; cout << "Total ways: "; cout << solve(n) << "\n"; } return 0; }

**Output:**

Enter number of test cases: 3 Enter Nth stair: 1 Total ways: 1 Enter Nth stair: 2 Total ways: 2 Enter Nth stair: 4 Total ways: 7

**C++ Implementation (Dynamic Programming Approach):**

(a) Top Down Approach:

#include <bits/stdc++.h> using namespace std; typedef long long ll; //initialize dp state. ll dp[100005]; //solve function which will return //total ways for nth stair. ll solve(ll n) { //base case if we are at bottom. if (n == 0) return 1; //base case if negative stair is //encountered. if (n < 0) return 0; //check if already calculated or not. if (dp[n] != -1) return dp[n]; //base case. if (n <= 2) return 1; else if (n >= 3) //other cases as nth stair depends //previous three stairs as well. return dp[n] = solve(n - 1) + solve(n - 2) + solve(n - 3); } int main() { cout << "Enter number of test cases: "; ll t; cin >> t; while (t--) { cout << "Enter Nth stair: "; ll n; //fill all dp state with -1 initially. memset(dp, -1, sizeof(dp)); cin >> n; cout << "Total ways: "; cout << solve(n) << "\n"; } return 0; }

**Output:**

Enter number of test cases: 3 Enter Nth stair: 10 Total ways: 193 Enter Nth stair: 20 Total ways: 85525 Enter Nth stair: 30 Total ways: 37895489

**(b) Bottom Up Approach**

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { cout << "Enter number of test cases: "; ll t; cin >> t; while (t--) { cout << "Enter Nth stair: "; ll n; cin >> n; //create dp state. ll dp[n + 1]; //base cases. dp[0] = 1; dp[1] = dp[2] = 1; //iterate through all stairs. for (ll i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; cout << "Total ways: "; cout << dp[n] << "\n"; } return 0; }

**Output:**

Enter number of test cases: 3 Enter Nth stair: 7 Total ways: 31 Enter Nth stair: 8 Total ways: 57 Enter Nth stair: 5 Total ways: 9

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions