Codility FrogJmp strange Java score
So I decided to give Codility a try . The first challenge - FrogJmp was ridiculous, but to my surprise I got 44%. The solution, even if correct, was clearly not acceptable from a performance standpoint.
Original solution:
public int solution2(int X, int Y, int D) {
return (int) Math.ceil((float)(Y -X)/D);
}
So I decided to try it with some other code without floating point arithmetic.
public int solution(int X, int Y, int D) {
int diff = Y - X;
if (diff % D == 0)
return diff /D;
else
return diff/D + 1;
}
This time I got 100%. So I wanted to test the performance myself and wrote a simple test:
class Solution {
public int solution(int X, int Y, int D) {
int diff = Y - X;
if (diff % D == 0)
return diff /D;
else
return diff/D + 1;
}
public int solution2(int X, int Y, int D) {
return (int) Math.ceil((float)(Y -X)/D);
}
private static Random ran = new Random(System.currentTimeMillis());
public static int getRandom(int a, int b){
return ran.nextInt(b - a + 1) + a;
}
public static void main(String[] args) {
int size = 1000_000;
int max = 1000_000_000;
int[] xs = new int[size];
int[] ys = new int[size];
int[] ds = new int[size];
for (int i = 0; i < size; i++) {
int y = getRandom(1, max);
int x = getRandom(1, y);
int d = getRandom(1, max);
xs[i] = x;
ys[i] = y;
ds[i] = d;
}
long start = System.nanoTime();
Solution sol = new Solution();
for (int i = 0; i < size; i++) {
sol.solution2(xs[i], ys[i], ds[i]);
}
long diff = System.nanoTime() - start;
System.out.println("took: " + diff/1000000 + "ms");
}
}
To my surprise, on my machine, solution 1 takes an average of 13ms and solution 2 (which is considered completely ineffective) 10ms.
What am I missing?
Perhaps he should do something about the expected complexity of the tasks of time and space.
expected worst-case time complexity - O (1); expected worst-case complexity O (1).
Doesn't solution 2 have constant time and space complexity?
Also I cannot understand this report of results for 44% solution:
What does it mean?
source to share
Both solutions have O (1) time complexity. The problem is that the first solution returns incorrect answers. Performance tests check the response as well as the timing. Your solution failed due to issues using float.
With x = 1, y = 1,000,000,000, d = 1, your first solution gives 1,000,000,000 as the answer and the second gives 999999999. Changing from (float)
to (double)
fixes that result.
In these tests of algorithms, it is generally recommended to avoid floating point arithmetic as much as possible in order to make it easier to get accurate answers for all cases.
source to share