Given the number N which denotes the number of stairs, the task is to reach the Nth stair by taking 1, 2 steps any number of times and 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,
There are only two possible ways: (1, 3) or (3, 1)Input: N = 5
Output: 5
Explanation:
Since a step of 3 has to be taken compulsorily and only once,
There are only 5 possible ways:
(1, 1, 3), (1, 3, 1), (3, 1, 1), (2, 3), (3, 2)
Approach: This problem can be solved using Dynamic Programming. To Reach Nth stair the person should be on (N – 1)th, (N – 2)th or (N – 3)th. So, To reach Nth stair from the base Reach (N – 1)th stair which includes exact only one step of 3, Reach (N – 2)th step with the steps which includes exactly one step of 3 and Reach the (N – 3)th step without taking any step of 3.
So, The Recurrence Relation for this problem will be –
includes_3[i] = includes_3[i-1] + includes_3[i-2] + not_includes[i-3]
whereas, the Recurrence relation when the 3 number of steps at a time is not allowed is
not_includes[i] = not_includes[i – 1] + not_includes[i – 2]
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, 2 step at a time and// 3 Steps at a time exactly once.#include <iostream>using namespace std;// Function to find the number// the number of ways to reach Nth stairint number_of_ways(int n){ // Array including number // of ways that includes 3 int includes_3[n + 1] = {}; // Array including number of // ways that doesn't includes 3 int not_includes_3[n + 1] = {}; // Initially to reach 3 stairs by // taking 3 steps can be // reached by 1 way includes_3[3] = 1; not_includes_3[1] = 1; not_includes_3[2] = 2; not_includes_3[3] = 3; // Loop to find the number // the number of ways to reach Nth stair for (int i = 4; i <= n; i++) { includes_3[i] = includes_3[i - 1] + includes_3[i - 2] + not_includes_3[i - 3]; not_includes_3[i] = not_includes_3[i - 1] + not_includes_3[i - 2]; } return includes_3[n];}// Driver Codeint main(){ int n = 7; cout << number_of_ways(n); return 0;} |
Java
// Java implementation to find the number// the number of ways to reach Nth stair// by taking 1, 2 step at a time and// 3 Steps at a time exactly once.class GFG{// Function to find the number// the number of ways to reach Nth stairstatic int number_of_ways(int n){ // Array including number // of ways that includes 3 int []includes_3 = new int[n + 1]; // Array including number of // ways that doesn't includes 3 int []not_includes_3 = new int[n + 1]; // Initially to reach 3 stairs by // taking 3 steps can be // reached by 1 way includes_3[3] = 1; not_includes_3[1] = 1; not_includes_3[2] = 2; not_includes_3[3] = 3; // Loop to find the number // the number of ways to reach Nth stair for (int i = 4; i <= n; i++) { includes_3[i] = includes_3[i - 1] + includes_3[i - 2] + not_includes_3[i - 3]; not_includes_3[i] = not_includes_3[i - 1] + not_includes_3[i - 2]; } return includes_3[n];}// Driver Codepublic static void main(String[] args){ int n = 7; System.out.print(number_of_ways(n));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to find the number# the number of ways to reach Nth stair# by taking 1, 2 step at a time and# 3 Steps at a time exactly once.# Function to find the number# the number of ways to reach Nth stairdef number_of_ways(n): # Array including number # of ways that includes 3 includes_3 = [0]*(n + 1) # Array including number of # ways that doesn't includes 3 not_includes_3 = [0] * (n + 1) # Initially to reach 3 stairs by # taking 3 steps can be # reached by 1 way includes_3[3] = 1 not_includes_3[1] = 1 not_includes_3[2] = 2 not_includes_3[3] = 3 # Loop to find the number # the number of ways to reach Nth stair for i in range(4, n + 1): includes_3[i] = includes_3[i - 1] + \ includes_3[i - 2] + \ not_includes_3[i - 3] not_includes_3[i] = not_includes_3[i - 1] + \ not_includes_3[i - 2] return includes_3[n]# Driver Coden = 7print(number_of_ways(n))# This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the number// the number of ways to reach Nth stair// by taking 1, 2 step at a time and// 3 Steps at a time exactly once.using System;class GFG{// Function to find the number// the number of ways to reach Nth stairstatic int number_of_ways(int n){ // Array including number // of ways that includes 3 int []includes_3 = new int[n + 1]; // Array including number of // ways that doesn't includes 3 int []not_includes_3 = new int[n + 1]; // Initially to reach 3 stairs by // taking 3 steps can be // reached by 1 way includes_3[3] = 1; not_includes_3[1] = 1; not_includes_3[2] = 2; not_includes_3[3] = 3; // Loop to find the number // the number of ways to reach Nth stair for (int i = 4; i <= n; i++) { includes_3[i] = includes_3[i - 1] + includes_3[i - 2] + not_includes_3[i - 3]; not_includes_3[i] = not_includes_3[i - 1] + not_includes_3[i - 2]; } return includes_3[n];}// Driver Codepublic static void Main(String[] args){ int n = 7; Console.Write(number_of_ways(n));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation to find the number// the number of ways to reach Nth stair// by taking 1, 2 step at a time and// 3 Steps at a time exactly once.// Function to find the number// the number of ways to reach Nth stairfunction number_of_ways(n){ // Array including number // of ways that includes 3 let includes_3 = new Uint8Array(n + 1); // Array including number of // ways that doesn't includes 3 let not_includes_3 = new Uint8Array(n + 1); // Initially to reach 3 stairs by // taking 3 steps can be // reached by 1 way includes_3[3] = 1; not_includes_3[1] = 1; not_includes_3[2] = 2; not_includes_3[3] = 3; // Loop to find the number // the number of ways to reach Nth stair for (let i = 4; i <= n; i++) { includes_3[i] = includes_3[i - 1] + includes_3[i - 2] + not_includes_3[i - 3]; not_includes_3[i] = not_includes_3[i - 1] + not_includes_3[i - 2]; } return includes_3[n];}// Driver Code let n = 7; document.write(number_of_ways(n));// This code is contributed by Surbhi Tyagi.</script> |
Output
20
Time complexity: O(n) where N is given the number of stairs
Auxiliary space: O(n)
Efficient approach: Space Optimization O(1)
The above approach includes_3 and not_includes_3, each of size n + 1. However, we can observe that at any given point in the loop, we only need the values of the arrays for the current iteration and the previous two iterations. So to optimize the space complexity, we can replace the arrays with three variables that store the necessary values.
Implementation Steps:
- Initialize variables: in1, in2, in3, incurr, not_in1, not_in2, not_in3, not_incurr.
- Set the initial value of in3 to 1.
- Iterate from i = 4 to n.
- Calculate the current value of incurr by summing the previous values of in3, in2, and not_in1.
- Calculate the current value of not_incurr by summing the previous values of not_in3 and not_in2.
- Update variables for the next iteration by shifting the values.
- Return the final value of incurr.
Implementation:
C++
#include <iostream>using namespace std;// Function to find the number// the number of ways to reach Nth stairint number_of_ways(int n){ int in1, in2 = 0, in3, incurr; int not_in1 = 1, not_in2 = 2, not_in3 = 3, not_incurr; in3 = 1; // Set the initial value for in3 for (int i = 4; i <= n; i++) { // Calculate the current value for incurr by summing the previous values incurr = in3 + in2 + not_in1; // Calculate the current value for not_incurr by summing the previous values not_incurr = not_in3 + not_in2; // Update the variables for the next iteration in1 = in2; in2 = in3; in3 = incurr; not_in1 = not_in2; not_in2 = not_in3; not_in3 = not_incurr; } return incurr; // Return the final result}// Driver Codeint main(){ int n = 7; cout << number_of_ways(n); // Print the result return 0;} |
Java
public class Staircase { // Function to find the number of ways to reach the Nth // stair /* * This function calculates the number of ways to reach * the Nth stair by taking 1, 2, or 3 steps at a time. * * @param n The Nth stair to reach. * * @return The number of ways to reach the Nth stair. */ static int numberOfWays(int n) { int in1 = 0, in2 = 0, in3 = 1, incurr = 0; int not_in1 = 1, not_in2 = 2, not_in3 = 3, not_incurr = 0; in3 = 1; // Set the initial value for in3 for (int i = 4; i <= n; i++) { // Calculate the current value for incurr by // summing the previous values incurr = in3 + in2 + not_in1; // Calculate the current value for not_incurr by // summing the previous values not_incurr = not_in3 + not_in2; // Update the variables for the next iteration in1 = in2; in2 = in3; in3 = incurr; not_in1 = not_in2; not_in2 = not_in3; not_in3 = not_incurr; } return incurr; // Return the final result } // Driver Code public static void main(String[] args) { int n = 7; System.out.println( numberOfWays(n)); // Print the result }} |
Python3
# Function to find the number# of ways to reach Nth stairdef number_of_ways(n): in1, in2 = 0, 0 in3, incurr = 1, 0 not_in1, not_in2, not_in3, not_incurr = 1, 2, 3, 0 in3 = 1 # Set the initial value for in3 for i in range(4, n + 1): # Calculate the current value for incurr by summing the previous values incurr = in3 + in2 + not_in1 # Calculate the current value for not_incurr by summing the previous values not_incurr = not_in3 + not_in2 # Update the variables for the next iteration in1, in2, in3 = in2, in3, incurr not_in1, not_in2, not_in3 = not_in2, not_in3, not_incurr return incurr # Return the final result# Driver Codedef main(): n = 7 print(number_of_ways(n)) # Print the resultmain() |
C#
using System;class Program { // Function to find the number of ways to reach the Nth // stair static int NumberOfWays(int n) { int in2 = 0, in3 = 1, incurr; int not_in1 = 1, not_in2 = 2, not_in3 = 3, not_incurr; incurr = 0; // Initialize incurr not_incurr = 0; // Initialize not_incurr for (int i = 4; i <= n; i++) { // Calculate the current value for incurr by // summing the previous values incurr = in3 + in2 + not_in1; // Calculate the current value for not_incurr by // summing the previous values not_incurr = not_in3 + not_in2; // Update the variables for the next iteration in2 = in3; in3 = incurr; not_in1 = not_in2; not_in2 = not_in3; not_in3 = not_incurr; } return incurr; // Return the final result } // Driver Code static void Main() { int n = 7; Console.WriteLine( NumberOfWays(n)); // Print the result }} |
Javascript
// Function to find the number// the number of way to reach Nth stairfunction numberOfWays(n) { let in1, in2 = 0, in3, inCurr; let not_in1 = 1, not_in2 = 2, not_in3 = 3, not_inCurr; in3 = 1; // Set the initial value for in3 for (let i = 4; i <= n; i++) { // Calculate the current value for inCurr by summing the previous values inCurr = in3 + in2 + not_in1; // Calculate the current value for not_inCurr by summing the previous values not_inCurr = not_in3 + not_in2; // Update the variables for the next iteration in1 = in2; in2 = in3; in3 = inCurr; not_in1 = not_in2; not_in2 = not_in3; not_in3 = not_inCurr; } return inCurr; // Return the final result}// Driver Codefunction main() { const n = 7; console.log(numberOfWays(n)); // Print the result}main(); |
Output:
20
Time complexity: O(n) where N is given the number of stairs
Auxiliary space: O(1)
Similar Article: Count ways to reach Nth Stair using 1, 2 or 3 steps at a time
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!
