Count ways to reach the nth stair

Posted by N.K. Chauhan on Mar 31, 2024

There are n stairs, we need to find number of ways a person can reach nth stair from bottom; if he can climb either 1 or 2 or 3 stairs at a time.

Example 1: No of ways to reach 4th stair

Input: 4
Output: 7

Example 2: No of ways to reach 7th stair

Input: 7
Output: 44


Solutions

Method 1: Recursion

As per the question the person can reach nth stair either taking 1 or 2 or 3 steps at a time, that means the person can reach nth stair either from (n-1)th stair or (n-2)nd stair or (n-3)rd stair. Now if we find number of ways a person can reach to n-1, n-2 and n-3 stair and add them, we should get the answer.

We also know that, the person is standing at 0th stair and reaching there is only possible in one way (just jumping), additionally there is no way to reach < 0 th stair; we can use these two as base condition.

package com.cb.recursion;

/*
 * Possible steps 1 or 2 or 3 at a time
 * */
public class R10_ReachNthStair {
    public static int noOfWays(int n) {
        if (n < 0)
            return 0;
        if (n == 0)
            return 1;

        return noOfWays(n - 1) + noOfWays(n - 2) + noOfWays(n - 3);
    }

    public static void main(String[] args) {
        System.out.println(noOfWays(4));
        System.out.println(noOfWays(7));
    }
}

7
44

Complexity

The time complexity of this solution is O(2^n) and space complexity is O(1).

Related


Calculate the Power of a Number (n^p)

Sum of the digits of a given number

Print numbers from a given number to 0

Print spelling for a given number

Program to solve "Tower of Hanoi" problem

Calculate factorial of a given number

Program for printing nth Fibonacci Number

Print numbers from 0 to a given number

Check if an integer array is sorted or not

Write a program to reverse a string