Count Ways To Reach The N-th Stair Problem Statement

You are given a number of stairs, N. Starting at the 0th stair, you need to reach the Nth stair. Each time you can either climb one step or two steps. You have to return the number of distinct ways to climb from the 0th step to the Nth step.

Input:

The first line contains an integer 'T', representing the number of test cases. For each test case, there is a single integer 'N' denoting the number of stairs.

Output:

For each test case, print the number of distinct ways to climb to the top of the stairs. Since the result could be large, return it modulo 10^9+7. Output for each test case should be printed in a separate line.

Example:

Input:

N=3

Output:

3

Explanation:

There are three ways to climb to the third stair: (0, 1, 2, 3) by taking one step at a time, (0, 2, 3) by taking a two-step followed by a one-step, and (0, 1, 3) by taking a one-step followed by a two-step.

Constraints:

1 ≤ T ≤ 100

0 ≤ N ≤ 10¹⁸

Note:

You do not need to print anything. This has already been managed.

Question

Count Ways To Reach The N-th Stair Problem Statement

You are given a number of stairs, N. Starting at the 0th stair, you need to reach the Nth stair. Each time you can either climb one step or two steps. You have to return the number of distinct ways to climb from the 0th step to the Nth step.

Input:

The first line contains an integer 'T', representing the number of test cases. For each test case, there is a single integer 'N' denoting the number of stairs.

Output:

For each test case, print the number of distinct ways to climb to the top of the stairs. Since the result could be large, return it modulo 10^9+7. Output for each test case should be printed in a separate line.

Example:

Input:

N=3

Output:

Explanation:

There are three ways to climb to the third stair: (0, 1, 2, 3) by taking one step at a time, (0, 2, 3) by taking a two-step followed by a one-step, and (0, 1, 3) by taking a one-step followed by a two-step.

Constraints:

1 ≤ T ≤ 100
0 ≤ N ≤ 10¹⁸

Note:

You do not need to print anything. This has already been managed.

Accepted Answer

The problem involves finding the number of distinct ways to climb to the Nth stair by taking one or two steps at a time.

Use dynamic programming to solve this problem efficiently.
The number of ways to reach the Nth stair is the sum of the number of ways to reach the (N-1)th stair and the (N-2)th stair.
Handle large inputs by taking modulo 10^9+7 to avoid overflow.
Example: For N=3, there are 3 ways to climb to the third stair: (0, 1, 2, 3), (0, 2, 3), and (0, 1, 3).

Asked in Nagarro