Codility - Lesson 14 Binary Search Algorithm - 1. MinMaxDivision

Source Link:
https://codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/

Question:

You are given integers K, M and a non-empty zero-indexed array A consisting of N integers. Every element of the array is not greater than M. You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block. The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0. The large sum is the maximal sum of any block.

For example, you are given integers K = 3, M = 5 and array A such that:
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2  

The array can be divided, for example, into the following blocks:

• [2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
• [2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
• [2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
• [2, 1], [5, 1], [2, 2, 2] with a large sum of 6.

The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.

Write a function:
class Solution { public int solution(int K, int M, int[] A); }
that, given integers K, M and a non-empty zero-indexed array A consisting of N integers, returns the minimal large sum.

For example, given K = 3, M = 5 and array A such that:
A[0] = 2 A[1] = 1 A[2] = 5 A[3] = 1 A[4] = 2 A[5] = 2 A[6] = 2  
the function should return 6, as explained above.

Assume that:

• N and K are integers within the range [1..100,000];
• M is an integer within the range [0..10,000];
• each element of array A is an integer within the range [0..M].

Complexity:

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

Elements of input arrays can be modified.

My Solution:
Notes:
1. main idea:
// The goal is to find the "minimal large sum"
// We use "binary search" to find it (so, it can be fast)
// We assume that the "min max Sum" will be 
// between "min" and "max", each time we try "mid"   
2. 
for(int i=0; i<A.length; i++){
maxSum = maxSum + A[i]; // maxSum: sum of all elements
minSum = Math.max(minSum, A[i]); // minSum: at least one max element 
}
3. the max one must be an "ok" result
int possibleResult = maxSum; 
4. do "binary search" (search for better Sum)
while(minSum <= maxSum){
int midSum = (minSum + maxSum) /2; 
boolean ok = checkDivisable(midSum, K, A);
if(ok == true){
possibleResult = midSum;
maxSum = midSum - 1; 
}
else{ 
minSum = midSum + 1;
}
}
5.
return possibleResult;
6. check if it can be divided by using the minMaxSum = "mid", into K blocks ?
public boolean checkDivisable(int mid, int k, int[] a)

Codility - Lesson 14 Binary Search Algorithm

Source Link:
https://codility.com/programmers/lessons/14-binary_search_algorithm/

Some Notes:
The binary search is a simple and very useful algorithm whereby many linear algorithms can
be optimized to run in logarithmic time.

In a binary search we use the information that all the elements are sorted.

Let’s see how the number of candidates is reduced, for example for the value x = 31.



For every step of the algorithm we should remember the beginning and the end of the remaining
slice of the array (respectively, variables beg and end). 

The middle element of the slice can easily be calculated as mid = (beg+end) / 2.

14.1: Binary search in O(log n).
1 def binarySearch(A, x):
2 n = len(A)
3 beg = 0
4 end = n - 1
5 result = -1
6 while (beg <= end):
7 mid = (beg + end) / 2
8 if (A[mid] <= x):
9 beg = mid + 1
10 result = mid
11 else:
12 end = mid - 1
13 return result

In subsequent iterations the number of candidates is halved, so the time complexity is O(log n).

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;