Codility - Lesson 13 Fibonacci Numbers - 2. FibFrog

Source Link:
https://codility.com/programmers/lessons/13-fibonacci_numbers/fib_frog/

Question:

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 a zero-indexed 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:
class Solution { public int solution(int[] A); }
that, given a zero-indexed 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.

Assume that:

• 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.

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

My Solution:
Notes:
1. for using "point" (java.awt.*)
import java.awt.*;
2. note: cannot use "List" (both java.util.* and java.awt.* have "List")
ArrayList<Integer> fibonacci = new ArrayList<>();
fibonacci.add(0); // note: f(0) = 0 (as in the quesion)
fibonacci.add(1);  
3. note: using "while" is better than "for" (avoid errors)
while(true){
int temp1 = fibonacci.get( fibonacci.size()-1 );
int temp2 = fibonacci.get( fibonacci.size()-2 );
fibonacci.add( temp1 + temp2 ); 
if(temp1 + temp2 > A.length){ 
break;
}
}
4. reverse "List": from big to small
Collections.reverse(fibonacci);
5. use "queue" with "point"
// point(x,y) = point("position", "number of steps")
ArrayList<Point> queue = new ArrayList<>(); 
queue.add( new Point(-1, 0) ); // position:-1, steps:0 
6.
while(true){
// cannot take element from queue anymore
if(index == queue.size() ){ 
return -1;
}
// take element from queue
// from big to small 
// case 1: "reach the other side" 
// case 2: "cannot jump"
// case 3: "can jump"
// take "next element" from queue
} 

Codility - Lesson 13 Fibonacci Numbers - 1. Ladder

Source Link:
https://codility.com/programmers/lessons/13-fibonacci_numbers/ladder/

Question:

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:
class Solution { public int[] solution(int[] A, int[] B); }
that, given two non-empty zero-indexed 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.

Assume that:

• 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].

Complexity:

• expected worst-case time complexity is O(L);
• expected worst-case space complexity is O(L), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified. 

My Solution:
Notes:

1. The task is to find out the number of ways someone can climb up a ladder of N rungs by ascending one or two rungs at a time. 
// It is not very hard to see that this number is just the "Fibonacci number of order N"
2. we implemented an easy dynamic programming approach to compute Fibonacci numbers
// this will take complexity O(n)
3. I use binary operators to keep track of "N modulo 2^{30}"
// otherwise. the Fibonacci numbers will cause a memory overflow (be careful~!!)
// and we are also asked to return "numbers modulo some power of 2" 
4. determine the "max" for Fibonacci
int[] fibonacci = new int[max+1];  
// plus one for "0"
5. initial setting of Fibonacci (importnat)
fibonacci[0] =1;
fibonacci[1] =1;
6. 
for(int i=2; i<= max; i++){
fibonacci[i] = (fibonacci[i-1] + fibonacci[i-2]) % (1 << 30);
// we want to find the result of "a number modulo 2^P"
// if we first let the number modulo 2^Q (Q > P) 
// then, modulo 2^P, the result is the same.
// So, "we first modulo 2^30" to avoid overflow
// where, 2^30 == 1 << 30     
}
7. to find "results"
for(int i=0; i<L; i++){
results[i] = fibonacci[A[i]] % (1 << B[i]);  
// where, "1 << B[i]" means 2^B[i]
}
8.
return results;

Codility - Lesson 13 Fibonacci Numbers

Source Link:
https://codility.com/programmers/lessons/13-fibonacci_numbers/

Some Notes: 
The first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.



The first twelve Fibonacci numbers are:



Notice that recursive enumeration as described by the definition is very slow.

Enumeration of the Fibonacci numbers can be done faster simply by using a basis of dynamic programming. 

We can calculate the values F0, F1, . . . ,Fn based on the previously calculated numbers (it is sufficient to remember only the last two values).

13.2: Finding Fibonacci numbers dynamically.
1 def fibonacciDynamic(n):
2 fib = [0] * (n + 2)
3 fib[1] = 1
4 for i in xrange(2, n + 1):
5 fib[i] = fib[i - 1] + fib[i - 2]
6 return fib[n]

The time complexity of the above algorithm is O(n).