Codility Frog Jump - Count minimal number of jumps from position X to Y

Question

Here is a question I tried from the Codility train website:

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D. Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

class Solution { public int solution(int X, int Y, int D); }

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

X = 10 Y = 85 D = 30

the function should return 3, because the frog will be positioned as follows: after the first jump, at position 10 + 30 = 40 after the second jump, at position 10 + 30 + 30 = 70 after the third jump, at position 10 + 30 + 30 + 30 = 100

Assume that:
X, Y and D are integers within the range [1..1,000,000,000];
X ≤ Y.
Complexity:
expected worst-case time complexity is O(1);
expected worst-case space complexity is O(1).

This is the solution I gave which fetched me 50% and time complexity of O(Y-X). Can anyone please suggest a better solution?

class Solution {
//X=start, Y=end, D=distance for code clarity
public int solution(int start, int end, int distance) {

// write your code in Java SE 7
int progress = start;
int count=0;
while(progress<end) {
progress=progress+distance;
count++;
}
return count;
}
}

Answer 1

You don't need a loop for this, there is a mathematical solution:

• If y - x is divisible by d, then it takes (y - x) / d jumps
• If y - x is not divisible by d, then it takes (y - x) / d + 1 jumps

In other words:

if ((y - x) % d == 0) {
    return (y - x) / d;
}
return (y - x) / d + 1;

Or the somewhat less readable but more compact:

return (y - x) / d + ((y - x) % d == 0 ? 0 : 1);

Answer 2

Indentation

Indentation is the first step to have code that is readable. Your code should look like this :

class Solution {
    // X=start, Y=end, D=distance for code clarity
    public int solution(int start, int end, int distance) {

        // write your code in Java SE 7
        int progress = start;
        int count = 0;
        while (progress < end) {
            progress = progress + distance;
            count++;
        }
        return count;
    }
}

Addition

Do know that

progress = progress + distance;

is the same as

progress += distance;

Visibility

Currently, your class Solution don't have an access modifier. Normally you should specify one, unless you really need the default one. Here is a little tutorial. In your case your class should probably be declare like this :

public class Solution {

Comments

Your first comments is what I would consider a good comments. It explains why the name are not what the problem specified, which is a good thing to note. The problem is, if you change the variable name again, you need to remember to change the comment.

The second comments is just noise. You should remove it.

Answer 3

Maybe you should try something like:

public class Frog {
    public static int solution(int x, int y, int d) {
        return (int) Math.ceil((y - x) / (float)d);
    }