How many possible ways the child can run up the ladder

A child is running up a ladder with n steps, and can hop either 1 step or 2 steps at a time. Calculate how many possible ways the child can run up the ladder.

This problem is similar to Fibonacci Problem. Each step n can be reached from either two steps below (n-2) or one step below (n-1), thus the number of possibilities to reach that step is the sum of the possibilities to reach those other two steps. Base cases would be:

1. If there is only 1 step then child can run up the ladder only one way by taking 1 step.
2. If there are 2 steps then child can run up the ladder 2 ways by taking a single 2 step or taking two 1 steps.

int countWays(int n)
{
    if(n==0)
        return 0;
    else if(n==1||n==2)
        return n;
    else
        return countWays(n-1)+countWays(n-2);
}

Like the Fibonacci problem,the runtime of this problem is exponential O(2^n)

One Thought on “How many possible ways the child can run up the ladder

  1. My Solution

    //starts from n = 0 and has to reach n = N. Everytime it is able to reach there,
    //one unique path is found.
    int countWays(int n, final int N){
    if (n > N) //over shoots
    { return 0; }

    else if(n == N)// reaches the top, or climbs exactly N steps
    { return 1; } //one unique way

    else{ //for current n, find no of unique ways from n+1 and n+2 to reach N
    return countWays(n+1,N) + countWays(n+2,N);
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation