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)
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).
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
}
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 2P, 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 2B[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;