Count Ways to Reach the N-th Stair Problem Statement

You are provided with a number of stairs, and initially, you are located at the 0th stair. You need to reach the Nth stair, and you can climb one or two steps at a time. Your task is to determine the number of distinct ways to climb from the 0th to the Nth stair.

Input:

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

Output:

For each test case, print the number of distinct ways to reach the Nth stair, modulo 10^9+7. The result for each test case should be on a new line.

Example:

Input:

N=3

Output:

The number of distinct ways to reach the 3rd stair is 3, considering all possible sequences of climbing as shown in the example.

Constraints:

1

Question

Count Ways to Reach the N-th Stair Problem Statement

You are provided with a number of stairs, and initially, you are located at the 0th stair. You need to reach the Nth stair, and you can climb one or two steps at a time. Your task is to determine the number of distinct ways to climb from the 0th to the Nth stair.

Input:

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

Output:

For each test case, print the number of distinct ways to reach the Nth stair, modulo 10^9+7. The result for each test case should be on a new line.

Example:

Input:

N=3

Output:

The number of distinct ways to reach the 3rd stair is 3, considering all possible sequences of climbing as shown in the example.

Constraints:

1 <= T <= 100
0 <= N <= 10^18

Note:

You are not required to print anything yourself; the output handling is managed by the system.

Accepted Answer

The problem involves determining the number of distinct ways to climb from the 0th to 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 based on the number of ways to reach the previous two stairs.
Consider base cases for 0th and 1st stair.
Keep track of the number of ways modulo 10^9+7 to avoid overflow issues.

Accepted Answer

You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair. Each time you can either climb one step or two steps. You are supposed to return the number of distinct ways in which you can climb from the 0th step to Nth step.
Example :
N=3
Example

We can climb one step at a time i.e. {(0, 1) ,(1, 2),(2,3)} or we can climb the first two-step and then one step i.e. {(0,2),(1, 3)} or we can climb first one step and then two step i.e. {(0,1), (1,3)}.
Input format :
The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow. The first and the only argument of each test case contains an integer 'N', representing the number of stairs.
Output format :
For each test case/query, print the number of distinct ways to reach the top of stairs. Since the number can be huge, so return output modulo 10^9+7. Output for every test case will be printed in a separate line.

Accepted Answer

Count Ways To Reach The N-th Stairs
You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair. Each time you can either climb one step or two steps. You are supposed to return the number of distinct ways in which you can climb from the 0th step to Nth step.
Example :
N=3
Example

We can climb one step at a time i.e. {(0, 1) ,(1, 2),(2,3)} or we can climb the first two-step and then one step i.e. {(0,2),(1, 3)} or we can climb first one step and then two step i.e. {(0,1), (1,3)}.
Input format :
The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow. The first and the only argument of each test case contains an integer 'N', representing the number of stairs.
Output format :
For each test case/query, print the number of distinct ways to reach the top of stairs. Since the number can be huge, so return output modulo 10^9+7. Output for every test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of.
Constraints :
1 <= T <= 100 0 <= N <= 10^18 Where 'T' is the number of test cases, and 'N' is the number of stairs.

1 Upvote

7 Answer

Accepted Answer

https://private-user-images.githubusercontent.com/77439575/313376594-dbf7f7d5-d352-4a55-a301-548d729964f8.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MTA1Njc5ODksIm5iZiI6MTcxMDU2NzY4OSwicGF0aCI6Ii83NzQzOTU3NS8zMTMzNzY1OTQtZGJmN2Y3ZDUtZDM1Mi00YTU1LWEzMDEtNTQ4ZDcyOTk2NGY4LnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDAzMTYlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwMzE2VDA1NDEyOVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPTc2N2Y3ZjQ4Njc1YzYxZjI0MzhjMDVhMWU3MGMxOTYzMmViZmQ2NWUxYzlkZDMyY2U5MjBmYjU1ODJmOTg2MzMmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.rxXCsoMOmlRFjQYcIuq2cKipPHt-NQFvPByXbt-FlmE

Accepted Answer

(currStep -1)We can take the one-step from (currStep-1)