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