Count Ways To N’Th Stair(Order Does Not Matter)

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.

Examples :

Input: n = 4
Output: 3
Explanation: Three ways to reach at 4th stair. They are {1, 1, 1, 1}, {1, 1, 2}, {2, 2}.

Input: n = 5
Output: 3
Explanation: Three ways to reach at 5th stair. They are {1, 1, 1, 1, 1}, {1, 1, 2, 1} and {1, 2, 2}.

Expected Time Complexity: O(n)
Expected Space Complexity: O(n)

Constraints:
1 ≤ n ≤ 10⁴

Approach 01:

class Solution{
public:
  int nthStair(int n){
     return (1 + n/2);
  }
};

class Solution:
    def nthStair(self,n):
        return (1 + n//2)

Time Complexity

• Constant Time Calculation:

  The function calculates the result using a simple arithmetic operation: \( 1 + \frac{n}{2} \). Since this operation involves a single division and addition, it takes \( O(1) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(1) \), as the function completes in constant time regardless of the input size.

Space Complexity

• Space for Variables:

  The function uses a constant amount of space for storing the integer result of the arithmetic operation. Therefore, no additional space is required that depends on the input size.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), since the function only requires a fixed amount of space.