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 ≤ 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...
Spinny Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter