PROBLEM LINK:
Technical Club Interview
CodewithTC
Author: h4wk
Editorialist: qaseem_hasan_
DIFFICULTY:
EASY
PROBLEM:
This question is a standard variation of the Classical Number of ways to reach nth position on a ladder by using only one step or two step.
QUICK EXPLANATION:
We can compute the sum at every i using the recurrence relation that:
sumAt(i) = sumAt(i-1) + sumAt(i-2)
If observed this relation you would find this is the fibonacci relation. Hence the answer is the Nth fibonacci number.
SOLUTIONS:
This can be calculated in 2 easy ways: iteration approach or recursive approach.
Editorialist's Solution (iterative)
#include<iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int fibo[n+1] = {0}; //clear set values to 0
// Assume you're standing at level 1.
fibo[1] = 1; //there are 1 total ways to reach 1st level(actually standing)
fibo[2] = 1; //there are 1 total ways to reach 2nd level(taking one step)
for(int i=3;i<=n;i++) // start with 3rd level
{
fibo[i] = fibo[i-1] + fibo[i-2];
/*fibo[3] = fibo[2] + fibo[1]; i.e. number of ways to reach 3rd step is sum of ways to reach step 2(1 step) and step 1(1 step), that's why fibo[3] = 2
you can either make one jump/step from step 2 or two jumps from step 1.*/
}
printf("%d",fibo[n]); // simple print the accumulation of numbers of ways upto the level n, answer.
}
Editorialist's Solution (recursive)
#include<iostream>
using namespace std;
int fibo(int n){
if(n==0)
return 0;
if(n==1)
return 1;
return fibo(n-1) + fibo(n-2);
}
int main()
{
int n;
cin >> n;
int ans = fibo(n);
cout << ans;
}