Given an integer N number of stairs, the task is count the number ways to reach the Nth stair by taking 1 or 2 step any number of times but taking a step of 3 exactly once.
Examples:
Input: N = 4
Output: 2
Explanation:
Since a step of 3 has to be taken compulsorily and only once. So, there are only two possible ways: (1, 3) or (3, 1)
Input: N = 5
Output: 5
Explanation:
There are five possible ways to reach 5th stair: (2, 3), (3, 2), (1, 1, 3), (1, 3, 1), (3, 1, 1)
Approach: This problem can be solved using the concept of Permutations & Combinations. There is a constraint according to which 3 steps at a time have to be taken exactly once. The idea is to count the number of positions that are possible for 3 steps to be taken.
Now, the next task is to find the number of possible two-steps in the movement to Nth stair, which is (N – 3) / 2. In this way, all the possible ways will be covered if the count of two-step is incremented once at a time and for each step, all the possible combinations are calculated.
After Generalising the steps the possible combinations for each possible sequence will be
Ways = (Length of sequence)! * (Count of 2-step)!
------------------------------------------
(Count of 1-step)!
Algorithm:
- Initialize the length of the sequence to (N – 2).
- Initialize the count of 1-steps to (N – 3).
- Initialize the count of 2-steps to 0
- Initialize the possible count of 2-steps to (N-3)/2.
- Run a loop until the possible count of 2-steps is equal to the actual count of 2-steps.
- Find the possible number of ways with the help of the current length of the sequence, count of 1-steps, count of 2-steps and by above-given formulae.
- Reduce the length of the sequence by 1.
- Increase the count of 2-steps by 1
Below is the implementation of the above approach.
C++
// C++ implementation to find the number // the number of ways to reach Nth stair // by taking 1 or 2 steps at a time and // 3rd step exactly once#include <bits/stdc++.h>using namespace std;int factorial(int n) { // Single line to find factorial return (n == 1 || n == 0) ? 1 : n * factorial(n - 1); } // Function to find// the number of waysint ways(int n){ // Base Case if (n < 3) { return 0; } // Count of 2-steps int c2 = 0; // Count of 1-steps int c1 = n - 3; // Initial length of sequence int l = c1 + 1; int s = 0; // Expected count of 2-steps int exp_c2 = c1 / 2; // Loop to find the ways for // every possible sequence while (exp_c2 >= c2) { int f1 = factorial(l); int f2 = factorial(c1); int f3 = factorial(c2); int f4 = (f2 * f3); s += f1 / f4; c2 += 1; c1 -= 2; l -= 1; } return s;}// Driver codeint main(){ int n = 7; int ans = ways(n); cout << ans << endl; return 0;}// This code is contributed by coder001 |
Java
// Java implementation to find the number // the number of ways to reach Nth stair // by taking 1 or 2 steps at a time and // 3rd step exactly once class GFG {static int factorial(int n){ // Single line to find factorial return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);}// Function to find // the number of ways static int ways(int n){ // Base Case if (n < 3) { return 0; } // Count of 2-steps int c2 = 0; // Count of 1-steps int c1 = n - 3; // Initial length of sequence int l = c1 + 1; int s = 0; // Expected count of 2-steps int exp_c2 = c1 / 2; // Loop to find the ways for // every possible sequence while (exp_c2 >= c2) { int f1 = factorial(l); int f2 = factorial(c1); int f3 = factorial(c2); int f4 = (f2 * f3); s += f1 / f4; c2 += 1; c1 -= 2; l -= 1; } return s;}// Driver Codepublic static void main(String args[]){ int n = 7; int ans = ways(n); System.out.println(ans);}}// This code is contributed by rutvik_56 |
Python3
# Python3 implementation to find the number # the number of ways to reach Nth stair # by taking 1 or 2 steps at a time and # 3rd Step exactly onceimport math# Function to find# the number of waysdef ways(n): # Base Case if n < 3: return 0 # Count of 2-steps c2 = 0 # Count of 1-steps c1 = n-3 # Initial length of sequence l = c1 + 1 s = 0 # expected count of 2-steps exp_c2 = c1 / 2 # Loop to find the ways for # every possible sequence while exp_c2 >= c2: f1 = math.factorial(l) f2 = math.factorial(c1) f3 = math.factorial(c2) s += f1//(f2 * f3) c2 += 1 c1 -= 2 l -= 1 return s# Driver Codeif __name__ == "__main__": N = 7 print(ways(N)) |
C#
// C# implementation to find the number // the number of ways to reach Nth stair // by taking 1 or 2 steps at a time and // 3rd step exactly once using System;class GFG{ static int factorial(int n){ // Single line to find factorial return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);} // Function to find // the number of ways static int ways(int n){ // Base Case if (n < 3) { return 0; } // Count of 2-steps int c2 = 0; // Count of 1-steps int c1 = n - 3; // Initial length of sequence int l = c1 + 1; int s = 0; // Expected count of 2-steps int exp_c2 = c1 / 2; // Loop to find the ways for // every possible sequence while (exp_c2 >= c2) { int f1 = factorial(l); int f2 = factorial(c1); int f3 = factorial(c2); int f4 = (f2 * f3); s += f1 / f4; c2 += 1; c1 -= 2; l -= 1; } return s;}// Driver codestatic void Main() { int n = 7; int ans = ways(n); Console.WriteLine(ans);}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// JavaScript implementation to find the number// the number of ways to reach Nth stair// by taking 1 or 2 steps at a time and// 3rd step exactly oncefunction factorial(n){ // Single line to find factorial return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);}// Function to find// the number of waysfunction ways(n){ // Base Case if (n < 3) { return 0; } // Count of 2-steps let c2 = 0; // Count of 1-steps let c1 = n - 3; // Initial length of sequence let l = c1 + 1; let s = 0; // Expected count of 2-steps let exp_c2 = Math.floor(c1 / 2); // Loop to find the ways for // every possible sequence while (exp_c2 >= c2) { let f1 = factorial(l); let f2 = factorial(c1); let f3 = factorial(c2); let f4 = (f2 * f3); s += Math.floor(f1 / f4); c2 += 1; c1 -= 2; l -= 1; } return s;}// Driver code let n = 7; let ans = ways(n); document.write(ans);// This code is contributed by Surbhi Tyagi.</script> |
Output:
20
Performance Analysis:
- Time Complexity: As in the above approach, there is one loop to check the possible permutations for each sequence which can go up till (N-3) which takes O(N) time and to find the possible combinations it will take O(N), Hence the Time Complexity will be O(N2).
- Space Complexity: As in the above approach, there is no extra space used, Hence the space complexity will be O(1).
Note: The time complexity can be improved up to O(N) by precomputing the factorials for every number till N.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
