Explore
Placement Prep

Edit

Edit

# Count the total number of ways to reach the Nth stair | FACE Prep

Published on 11 Mar 2020

Program to count the total number of ways to reach the Nth stair is discussed here.

DESCRIPTION: There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time.

Count the total number of ways, the person can reach the top.

Sample Input:

4 (Number of stairs)

Sample Output:

5 (Number of ways)

Explanation:

Way 1: 1-1-1-1-1

Way 2: 1-2-1

Way 3: 2-1-1

Way 4: 1-1-2

Way 5: 2-2

## Algorithm to count the total number of ways to reach the Nth stair

• Input the total number of stairs.
• This problem is clearly recursive.
• The person can reach the Nth stair from the (N-1)th stair or (N-2)th stair.
• Recursively call, ways(n) = ways(n-1) + ways(n - 2)

## Program to count the total number of ways to reach the Nth stair

C++

Output
Input - 7 Output - 21

Test Case 1

I/P

4

O/P

5

Test Case 2

I/P

7

O/P

21

Test Case 3

I/P

24

O/P

75025

Test Case 4

I/P

2

O/P

2

Test Case 5

I/P

3

O/P

3