Asked in ACCOLITE and AMAZON
There are N stairs, and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top (order does not matter).
Note: Order does not matter means for n=4 {1 2 1},{2 1 1},{1 1 2} are considered same.
Example 1:
Input:
N = 4
Output: 3
Explanation: You can reach 4th stair in
3 ways.
3 possible ways are:
1, 1, 1, 1
1, 1, 2
2, 2
Example 2:
Input:
N = 5
Output: 3
Explanation:
You may reach the 5th stair in 3 ways.
The 3 possible ways are:
1, 1, 1, 1, 1
1, 1, 1, 2
1, 2, 2
Your Task:
Your task is to complete the function countWays() which takes single argument(N) and returns the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 106
CODE:
// ways to reach Nth stair
#include <bits/stdc++.h>
using namespace std;
// A simple recursive program to
// find N'th fibonacci number
int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways to
// reach s'th stair
int countWays(int s)
{
return fib(s + 1);
}
// Driver C
int main()
{
int s = 4;
cout << "Number of ways = " << countWays(s);
return 0;
}
ConversionConversion EmoticonEmoticon