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:
Firstline 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,
 We need an array of size equals the number of steps N.
 We initialize the first step with the value one.
 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.

For the steps those are greater than the 2^{nd} there is two possibilities,
 To reach the i^{th} step, we can go from the (i1) step.
 To reach the i^{th} step, we can go from the (i2) step.
Let f(i)= no. Of possible combination to reach the i^{th} step.
f(i)= f(i1) +f(i2)
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
TOP Interview Coding Problems/Challenges