Q:

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

mahmoud2506
Save to bookmark
|
2022-05-01
|
  256 
0

Find Total Ways to Reach Nth Stair from Bottom

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

Output:

Print the number of ways to reach nth 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
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | Recursion
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given the mobile numeric keypad. You can only pres... >>
<< Given a string, find out if the string is K-palind...