Climbing Stairs Problem using Mathematics
Note: This Method is only applicable for the question Count ways to N’th Stair (Order does not matter) .
Order does not matter means for n = 4 {1 2 1} ,{2 1 1} , {1 1 2} are considered same.
In this method, simply count the number of sets having 2, which will be equal to n/2. So total number of ways will be n/2+1 (one is added to incude the set which does not contain any 2)
Below is the implementation of above approach:
#include <iostream>
using namespace std;
int main()
{
int n;
n = 5;
// Here n/2 is done to count the number 2's in n
// 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
cout << "Number of ways when order of steps does not "
"matter is : "
<< 1 + (n / 2) << endl;
return 0;
}
import java.util.*;
class GFG {
public static void main(String[] args)
{
int n;
n = 5;
// Here n/2 is done to count the number 2's
// in n 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
System.out.print(
"Number of ways when order of steps "
+ "does not matter is : " + (1 + (n / 2)));
}
}
// This code is contributed by todaysgaurav
n = 5
# Here n/2 is done to count the number 2's in n
# 1 is added for case where there is no 2.
# eg: if n=4 ans will be 3.
# {1,1,1,1} set having no 2.
# {1,1,2} ans {2,2} (n/2) sets containing 2.
print("Number of ways when order "
"of steps does not matter is : ", 1 + (n // 2))
# This code is contributed by rohitsingh07052
using System;
class GFG {
static public void Main()
{
int n;
n = 5;
// Here n/2 is done to count the number 2's
// in n 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
Console.WriteLine(
"Number of ways when order of steps "
+ "does not matter is : " + (1 + (n / 2)));
}
}
// This code is contributed by Ankita saini
var n;
n = 5;
// Here n/2 is done to count the number 2's in n
// 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
console.log("Number of ways when order " +
"of steps does not matter is : ",
parseInt(1 + (n / 2)));
// This code is contributed by Ankita saini
Output
Number of ways when order of steps does not matter is : 3
Time Complexity : O(1)
Auxiliary Space : O(1)
Climbing Stairs to reach at the top.
There are n stairs, a person standing at the bottom wants to climb stairs to reach the nth stair. The person can climb either 1 stair or 2 stairs at a time, the task is to count the number of ways that a person can reach at the top.
Consider the example shown in the diagram. The value of n is 3. There are 3 ways to reach the top. The diagram is taken from Easier Fibonacci puzzles
Examples:
Input: n = 1
Output: 1 There is only one way to climb 1 stairInput: n=2
Output: 2 There are two ways: (1, 1) and (2)Input: n = 4
Output: 5 (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)