Problem

You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely: 

        - with your first step you can stand on rung 1 or 2,

        - if you are on rung K, you can move to rungs K + 1 or K + 2,

        - finally you have to stand on rung N.

Your task is to count the number of different ways of climbing to the top of the ladder. 

For example, given N = 4, you have five different ways of climbing, ascending by:

·         1, 1, 1 and 1 rung,

·         1, 1 and 2 rungs,

·         1, 2 and 1 rung,

·         2, 1 and 1 rungs, and

·         2 and 2 rungs.

Given N = 5, you have eight different ways of climbing, ascending by:

·         1, 1, 1, 1 and 1 rung,

·         1, 1, 1 and 2 rungs,

·         1, 1, 2 and 1 rung,

·         1, 2, 1 and 1 rung,

·         1, 2 and 2 rungs,

·         2, 1, 1 and 1 rungs,

·         2, 1 and 2 rungs, and

·         2, 2 and 1 rung. 

The number of different ways can be very large, so it is sufficient to return the result modulo 2^P, for a given integer P.

Write a function: 

    function solution(A, B);

that, given two non-empty arrays A and B of L integers, returns an array consisting of L integers specifying the consecutive answers; position I should contain the number of different ways of climbing the ladder with A[I] rungs modulo 2^B[I]. 

For example, given L = 5 and:

    A[0] = 4   B[0] = 3

    A[1] = 4   B[1] = 2

    A[2] = 5   B[2] = 4

    A[3] = 5   B[3] = 3

    A[4] = 1   B[4] = 1 

the function should return the sequence [5, 1, 8, 0, 1], as explained above.

Write an efficient algorithm for the following assumptions:

·         L is an integer within the range [1..50,000];

·         each element of array A is an integer within the range [1..L];

·         each element of array B is an integer within the range [1..30]. 

Note:

When N=3, there are three different ways of climbing, ascending by:

·         1, 1 and 1 rung,

·         1 and 2 rungs,

·         2 rungs and 1,

When N=4, there are five different ways of climbing, ascending by (from the question):

·         1, 1, 1 and 1 rung,

·         1, 1 and 2 rungs,

·         1, 2 and 1 rung,

·         2, 1 and 1 rungs, and

·         2 and 2 rungs. 

When N = 5, there are eight different ways of climbing, ascending by (from the question):

·         1, 1, 1, 1 and 1 rung,

·         1, 1, 1 and 2 rungs,

·         1, 1, 2 and 1 rung,

·         1, 2, 1 and 1 rung,

·         1, 2 and 2 rungs,

·         2, 1, 1 and 1 rungs,

·         2, 1 and 2 rungs, and

·         2, 2 and 1 rung.

The lesson for this problem is on Fibonacci numbers. It should occur to the candidate that Fibonacci numbers may be used somewhere, somehow in the solution. Fibonacci numbers from index 0 to index 15 are:

From the table, the Fibonacci number of index 4 is 3. Four is 3 + 1. Note that the number of ways of climbing a ladder of 3 rungs, according to the problem, is the Fibonacci number, 3, which is equal to the Fibonacci number of the index 4 = 3+1. 

From the table, the Fibonacci number of index 5 is 5. Five is 4 + 1. Note that the number of ways of climbing a ladder of 4 rungs, according to the problem, is the Fibonacci number, 5, which is equal to the Fibonacci number of the index 5= 4+1.

From the table, the Fibonacci number of index 6 is 8. Six is 5 + 1. Note that the number of ways of climbing a ladder of 5 rungs, according to the problem, is the Fibonacci number, 8, which is equal to the Fibonacci number of the index 6 = 5+1. 

So, the number of ways of climbing a ladder of N rungs is the Fibonacci number of the index, N+1.

When N is 4 for example, there are 5 ways. This is because the Fibonacci number for the index 4+1=5 is 5. However, the question does not want 5 as the answer. If P=3, then the question wants as answer, 

    5 % 2³ = 5 % 8 = 5  (because 5 ÷ 8 = 0 remainder 5)

If P=2, then the question wants as answer, 

    5 % 2² = 5 % 4 = 1  (because 5 ÷ 4 = 1 remainder 1)

By the question, the different values of the array, B are different values of P.

Maximum Fibonacci Number for this Problem

Two of the assumptions of the problem are:

·         L is an integer within the range [1..50,000];

·         each element of array A is an integer within the range [1..L]; 

This means that the maximum index is L+2, and the maximum Fibonacci number is fib(L+2).

Why L+2 ? - This is because, the while condition to produce the Fibonacci numbers below, is (k<L+2). If the maximum index is made L+1, then the while condition has to be (k<=L+1). 

Smart Solution

A solution() function and necessary code, is in the following program (read the code and comments):

<script type='text/javascript'>
    "use strict";

    function solution(A, B) {
        let L = A.length;

        let k;
        let max = L+2;     

        const fib = new Array(max);
        fib[0]=0;
        fib[1]=1;

        for(k=2;k<L+2;k++){
            fib[k]=fib[k-1]+fib[k-2];
        }

        const result = new Array(L);

        for (k=0;k<L;k++){
            let pw = Math.pow(2, B[k]);
            result[k] = fib[A[k]+1] % pw; 
        }

        return result;
    }


    const A = [4, 4, 5, 5, 1];
    const B = [3, 2, 4, 3, 1];

    let ret = solution(A, B);

    for (let i = 0; i < 5; ++i) {
        document.write(ret[i] + ' ');
    }

    document.write('<br>');

</script>

The output is:

    5 1 8 0 1 

as expected. Note that in determining the Fibonacci numbers, the for-loop iterated from k=2 to just less than L+2 (zero based indexing). The length is actually L+2, because of zero indexed based, and the plus 1 for the Fibonacci index in the solution.

At app.codility.com/programmers the scoring and detected time complexity for this solution() is: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(L)

app.codility.com/programmers must have ignored the time to produce the Fibonacci numbers. 

Thanks for reading.