Home » Interview coding problems/challenges

Step count problem | Find the number of possible combinations to reach the final step

Step count problem: Here, we are going to learn how to find the number of possible combinations to reach the final step?
Submitted by Souvik Saha, on June 28, 2020

Problem statement:

You are trying to climb on a staircase. There are N number of steps. You can only climb one or two steps at one time. Now you have to find out the number of possible combinations to reach the final step.

Input:
First-line contains T Testcases,
T no. of lines along with the step count(N).

E.g.
3
4
5
6

Output:
Print the number of possible valid steps 
to reach the last step.

Example

T = 3

Input:
4
Output:
5

Input:
5
Output:
8

Input:
6
Output:
13

Explanation with example:

To find out the possible combination to reach the last step is a problem of combination. We are using the Dynamic programming approach to solve it with less time complexity.

To solve this problem, we will follow these steps,

1. We need an array of size equals the number of steps N.
2. We initialize the first step with the value one.
3. Initialize the second step with two because you can take two steps to reach the second step or you can directly move to the second step. Therefore, in the second step there in two possibilities.
4. For the steps those are greater than the 2^nd there is two possibilities,
   1. To reach the i^th step, we can go from the (i-1) step.
   2. To reach the i^th step, we can go from the (i-2) step.

Let f(i)= no. Of possible combination to reach the ith step.
f(i)= f(i-1) +f(i-2)

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int count(int num)
{
    int arr[num];
    arr[0] = 1;
    arr[1] = 2;
    for (int i = 2; i < num; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[num - 1];
}

int main()
{
    int t;
    
    cout << "Testcase : ";
    cin >> t;
    
    while (t--) {
        int num;
    
        cout << "Enter the Steps : ";
        cin >> num;
    
        cout << "Step Count : " << count(num) << endl;
    }
    
    return 0;
}

Output

Testcase : 3
Enter the Steps : 5
Step Count : 8
Enter the Steps : 10
Step Count : 89
Enter the Steps : 7
Step Count : 21