Problem

The Fibonacci sequence is defined using the following recursive formula: 

    F(0) = 0

    F(1) = 1

    F(M) = F(M - 1) + F(M - 2) if M >= 2

A small frog wants to get to the other side of a river. The frog is initially located at one bank of the river (position -1) and wants to get to the other bank (position N). The frog can jump over any distance F(K), where F(K) is the K-th Fibonacci number. Luckily, there are many leaves on the river, and the frog can jump between the leaves, but only in the direction of the bank at position N. 

The leaves on the river are represented in an array A consisting of N integers. Consecutive elements of array A represent consecutive positions from 0 to N - 1 on the river. Array A contains only 0s and/or 1s:

        0 represents a position without a leaf;

        1 represents a position containing a leaf. 

The goal is to count the minimum number of jumps in which the frog can get to the other side of the river (from position -1 to position N). The frog can jump between positions -1 and N (the banks of the river) and every position containing a leaf.

For example, consider array A such that: 

    A[0] = 0

    A[1] = 0

    A[2] = 0

    A[3] = 1

    A[4] = 1

    A[5] = 0

    A[6] = 1

    A[7] = 0

    A[8] = 0

    A[9] = 0

    A[10] = 0

The frog can make three jumps of length F(5) = 5, F(3) = 2 and F(5) = 5. 

Write a function:

    function solution(A); 

that, given an array A consisting of N integers, returns the minimum number of jumps by which the frog can get to the other side of the river. If the frog cannot reach the other side of the river, the function should return -1.

For example, given: 

    A[0] = 0

    A[1] = 0

    A[2] = 0

    A[3] = 1

    A[4] = 1

    A[5] = 0

    A[6] = 1

    A[7] = 0

    A[8] = 0

    A[9] = 0

    A[10] = 0

the function should return 3, as explained above. 

Write an efficient algorithm for the following assumptions:

·         N is an integer within the range [0..100,000];

·          each element of array A is an integer that can have one of the following values: 0, 1.

Note: 

The first sixteen Fibonacci numbers are:

For this given problem and its data, 3 is the minimum number of jumps. 

N for the given data list is 11. The given data list is:

This array is scanned until the first value of 1 is met. The distance from -1 to this 1 at index 3 is 4, but 4 is not a Fibonacci number. The frog cannot jump to position 3. So the scanning continues till the next 1. At the next 1, the distance is 5 at index 4. Five is a Fibonacci number. The frog jumps to index 4. So the counter is given the value, 1. 

From this point to the next 1 at index 6, the distance is 2. Two is a Fibonacci number. The frog jumps to position 6. So the counter becomes 2. From index 6 to the bank of the river, there is no 1. The distance from index 6 to the bank of the river, which is index N = 11, is 5. Five is a Fibonacci number. The frog jumps to position N. So the counter becomes 3.

Remember: The goal is to count the MINIMUM number of jumps in which the frog can get to the other side of the river (from position -1 to position N). So there is a serious issue: just jumping to the nearest Fibonacci number beginning from -1, may not give the minimum number of jumps. The whole list has to be considered first, somehow. If the distance from position -1 to position N is a Fibonacci number, then the minimum number of jumps is 1. 

Strategy

There is an outer for-loop with an inner for-loop. The outer for-loop scans the given array, while the inner for-loop does some logic.

There is a Fibonacci array, of Fibonacci numbers of indexes from 0 to N+2. The +2 is for position -1 and the other bank, N+1 (=12 above). From the start or from a position on the river with a leaf, the inner for-loop determines if the distance from that position to the furthest 1 ahead, or to the other bank of the river, is a Fibonacci number. If it is, then the frog jumps to the new position or to the other bank of the river (depending on which would be faster). 

There is a counter array, where counting accumulates as the indexes increase, but the accumulation (or substitution) is not done in a conventional way (see code below).

So, one of the first thing the solution function does, is to produce the Fibonacci array. If the frog can jump from -1 to N (because the distance from -1 to N is a Fibonacci number), then that would be all, and the counter would be 1 (minimum number of jumps). 

Though Fibonacci numbers are normally defined as fibs[0] = 0, fibs[1] = 1, fibs[2] = 1, fibs[3] = 2, etc., in the solution function below,  they are used as fibs[0] = 1, fibs[1] = 2, fibs[2] = 3, fibs[3] = 5, etc. This is because 0 is not a jumping distance. It is also to avoid the ambiguity of F[1] = 1 and F[2] = 1. See table below.

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) {
        let N = A.length;

        let START = -1;

        const fibs = new Array(N+2);
        fibs[0] = 1;  
        fibs[1] = 2;
        for (let i = 2; i < fibs.length; i++) {
            fibs[i] = fibs[i-2] + fibs[i-1];
            if (fibs[i] == N+1)
                return 1;    //frog will be able to jump from -1 to N
        }

        const counter =  new Array(N+1).fill(0); 
        for (let i = START; i < N+1; i++) {    //above, 11+1 = 12
            if (i == START || counter[i] > 0) {    //position algorithm at current encountered index
                for (let j = 0; (i + fibs[j]) < N+1; j++) {    // fibs[i] == N+1, addressed above
                    // frog to jump "i+fibs[j]"
                    let nextPossibleIndex = i + fibs[j];

                    if (nextPossibleIndex == N || A[nextPossibleIndex] == 1) {
                        if (i == START)
                            counter[nextPossibleIndex] = 1;
                        else if (counter[nextPossibleIndex] == 0) 
                            counter[nextPossibleIndex] = counter[i] + 1;
                        else
                            counter[nextPossibleIndex] = Math.min(counter[nextPossibleIndex], counter[i] + 1);
                    }
                }
            }      
        }

        return counter[N] <= 0 ? -1 : counter[N];
    }


    const A = [0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0];

    let ret = solution(A);

    document.write(ret + '<br>');

</script>

The output is: 

    3

Note the use of the variable, START. 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(N * log(N))

The reader should read through the solution function again, to see how it ties with the following table:

The main algorithm used in the solution() function, is a kind of algorithm known as Greedy Algorithm. For more on that – see later.