Q:

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

mahmoud2506
Save to bookmark
|
2022-05-01
|
  257 
0

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

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
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

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 2nd there is two possibilities,
    1. To reach the ith step, we can go from the (i-1) step.
    2. To reach the ith 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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
An N pair array is given to you. In every pair, th... >>
<< Given a sequence of numbers you have to print the ...