Find Number of Ways to Reach the K-th Stair - Solution & Explanation

Input: k = 0

Output: 2

Explanation:

The 2 possible ways of reaching stair 0 are:

• Alice starts at stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
• Alice starts at stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
  • Using an operation of the second type, she goes up 2⁰ stairs to reach stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.

Input: k = 1

Output: 4

Explanation:

The 4 possible ways of reaching stair 1 are:

• Alice starts at stair 1. Alice is at stair 1.
• Alice starts at stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
  • Using an operation of the second type, she goes up 2⁰ stairs to reach stair 1.
• Alice starts at stair 1.
  • Using an operation of the second type, she goes up 2⁰ stairs to reach stair 2.
  • Using an operation of the first type, she goes down 1 stair to reach stair 1.
• Alice starts at stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
  • Using an operation of the second type, she goes up 2⁰ stairs to reach stair 1.
  • Using an operation of the first type, she goes down 1 stair to reach stair 0.
  • Using an operation of the second type, she goes up 2¹ stairs to reach stair 2.
  • Using an operation of the first type, she goes down 1 stair to reach stair 1.