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:

enter image description here

What does it mean?

+3


source to share


12 replies


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.

+2


source


Solution in Java 100/100 complexity and O (1).



public int solution(int X, int Y, int D) {
    return Double.valueOf(Math.ceil((Y - X) / (double) D)).intValue();
}

      

+2


source


Solution in Java 100/100:

public int solution(int X, int Y, int D) {
    int diff = Y - X;
    int count = diff / D;
    if (diff % D > 0) {
        count++;
    }
    return count;
}

      

+1


source


First, you must pay attention to the divisor, which cannot be 0 in your case " diff / D

" cannot be . D

0

Second, in your case, " diff = Y - X

" if (diff <= 0), you no longer need to jump.

0


source


Frogjump solution in C

int solution(int X, int Y, int D) {
        // write your code in C90
        int r=0;

        if(Y>X)
        {   
            r=(Y-X)/D;
            if((X+(r*D)) < Y) r++;
        }

        return r;
    }

      

0


source


Solution in C #

double result = (Y - X) / (D * 1.0);
return Convert.ToInt32(Math.Ceiling(result));

      

0


source


100/100 solution in C # I am just

using System;    
class Solution {
    public int solution(int X, int Y, int D) {        
        return ((Y - X) + D - 1)/D;        
    }
}

      

0


source


public static int solution(int X, int Y, int D) {
        // write your code in Java SE 8


       return (int)Math.round((Y-X)/(double)D);

    }

      

This will also result in 100%

0


source


public int solution(int X, int Y, int D) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    double divAll = (Y-X) / (D * 1.0);
    double finalRes = (Y-X) % (D * 1.0) > 0 ? (divAll + 1) : divAll;

    return (int) finalRes;
}

      

0


source


Here is my 100% / 100% solution

public int solution(int X, int Y, int D) {
    double d = D;
    return (int) Math.ceil( (Y-X) / d );
}

      

0


source


I just solved it with a great score, so this is my answer (java):

static int solution(int X, int Y, int D){

    double count=((double)Y-(double)X)/(double) D;

    return (int)Math.ceil(count);
 }

      

First time I thought it might be rdone using "While loops", but I got zero performance.

0


source


Tried this one for 100/100

public static int frogJmp(int X, int Y, int D) {
    return (int) Math.ceil( (Y-X) / (double)D );
}

      

0


source







All Articles