Count ways to reach the Nth stair using multiple 1 or 2 steps and a single step 3

0 0 6 minutes read

Given an integer N number of stairs, the task is count the number ways to reach the N^th 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 N^th 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 ways
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 code
int 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 Code
public 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 once
 
import math
 
# Function to find
# the number of ways
def 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 Code
if __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 code
static 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 once
 
function factorial(n)
{
 
    // Single line to find factorial
    return (n == 1 || n == 0) ? 1 :
            n * factorial(n - 1);
}
 
// Function to find
// the number of ways
function 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:

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(N²).
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 zambiatek!