# Stair Case: C++ program to solve the staircase problem

Here, we are going to implement a **C++ program to solve the staircase problem**.

Submitted by Indrajeet Das, on December 14, 2018

A child is running up a staircase with **N steps**, and can hop **1** step, **2** steps or **3** steps at a time. Implement a method to **count how many possible ways the child can run up to the stairs**? You need to return number of possible ways **W**.

**Input format:** Line 1: Integer N (No. of steps)

**Output Format:** Line 1: Integer W i.e. Number of possible ways

**Constraint:** (1 <= N <= 30)

**Sample Input 1:** 4

**Sample Output:** 7

**Explanation:**

In this question, to find out the **number of ways to we can climb the stairs**, we can use a recursive method to solve it. We can call the recursive function thrice in our code with parameters of **(N-1)**, **(N-2)** and **(N-3)** steps (the decrease in steps show the number of steps climbed). And add and return them.

It is one of the typical questions for recursive algorithms.

**Algorithm:**

- Step 1: Declare a recursive function staircase with one parameter (int steps).
- Step 2: Base Case:

if(steps <0) // No steps to climb

return 0; - Step 3: Base Case 2:

if(steps ==0) //Already reached top

return 1; - Step 4: Return staircase (steps -1) + staircase (steps – 2) + staircase (steps -3).

i.e. the total ways in which we can climb the steps.

**Example:**

For stairs = 3. Ways to climb are, 1 1 1 1 2 2 1 3 Hence there are four ways to climb.

**C++ program:**

#include<bits/stdc++.h> using namespace std; //Recursive Function int staircase(int n){ if(n<0){ //Base Case 1 return 0; } if(n==0){ //Base Case 2 return 1; } int count = 0; count += staircase(n-1); //Stepping 1 step count += staircase(n-2); //Stepping 2 step count += staircase(n-3); //Stepping 3 step return count; } //Main int main(){ int n; cout<<"Enter number of stairs"<<endl; cin>>n; cout<<"No of ways to climb stairs are "; cout<<staircase(n)<<endl; return 0; }

**Output**

Enter number of stairs 5 No of ways to climb stairs are 13

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.