Count Ways to Reach the Nth Stair

Given a number of stairs, starting from the 0th stair, calculate the number of distinct ways you can reach the Nth stair. You can climb either one step or two steps at a time.

Input:

The first line contains an integer 'T', representing the number of test cases.
Each test case consists of a single integer 'N', which denotes the number of stairs.

Output:

For each test case, print the number of distinct ways to reach the Nth stair modulo 10^9+7.
Each output should be printed on a separate line.

Example:

Input:
N = 3

Explanation:
You can climb stairs in the following distinct ways:
1. One step at a time: (0, 1), (1, 2), (2, 3)
2. Two steps at first, then one step: (0, 2), (1, 3)
3. One step then two steps: (0, 1), (1, 3)

Constraints:

1 ≤ T ≤ 100

0 ≤ N ≤ 10¹⁸

Note:

No need to print outputs, it is handled by the system.

Question

Count Ways to Reach the Nth Stair

Given a number of stairs, starting from the 0th stair, calculate the number of distinct ways you can reach the Nth stair. You can climb either one step or two steps at a time.

Input:

The first line contains an integer 'T', representing the number of test cases.
Each test case consists of a single integer 'N', which denotes the number of stairs.

Output:

For each test case, print the number of distinct ways to reach the Nth stair modulo 10^9+7.
Each output should be printed on a separate line.

Example:

Input:
N = 3

Example

Explanation:
You can climb stairs in the following distinct ways:
1. One step at a time: (0, 1), (1, 2), (2, 3)
2. Two steps at first, then one step: (0, 2), (1, 3)
3. One step then two steps: (0, 1), (1, 3)

Constraints:

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

Note:

No need to print outputs, it is handled by the system.

Accepted Answer

The question is about calculating the number of distinct ways to reach the Nth stair by climbing one or two steps at a time.

Use dynamic programming to solve this problem efficiently.
Define a recursive function to calculate the number of ways to reach each stair.
Consider base cases for 0 and 1 stairs.
Use memoization to store intermediate results and avoid redundant calculations.
Handle large values of N by taking modulo 10^9+7 of the final result.
Example: For N = 3, the number of distinct ways to reach the 3rd stair is 3.

Accepted Answer

static int countWays(int n)

{

int prev = 1;

int prev2 = 1;

for (int i = 2; i <= n; i++) {

int curr = prev + prev2;

prev2 = prev;

prev = curr;

}

return prev;

}

Time Complexcity : O(n)
Space Complexcity : O(1)

Asked in Spinny