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 ≤ 1018
Note:
No need to print outputs, it is handled by the system.
AnswerBot
4d
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...read more
Gopal Jain
1y
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 :...read more
Help your peers!
Add answer anonymously...
Top Spinny Software Engineer interview questions & answers
Popular interview questions of Software Engineer
Top HR questions asked in Spinny Software Engineer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app