TCINVW - EDITORIAL

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;
    }