15
\$\begingroup\$

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;
}
}
\$\endgroup\$
  • 5
    \$\begingroup\$ One word hint: "division". \$\endgroup\$ – Jerry Coffin Apr 9 '14 at 6:15
  • \$\begingroup\$ This ansver get score of 100: public int solution(int X, int Y, int D) { if(X == Y) return 0; int dist = Y - X; return dist%D == 0? dist/D: dist/D + 1; } \$\endgroup\$ – Vitaliy A Jul 3 '16 at 15:15
20
\$\begingroup\$

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);
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Brilliant, going by your first approach its best to check if the distance is zero so as to return x to prevent division by zero exception. \$\endgroup\$ – Siobhan May 23 '16 at 15:00
  • \$\begingroup\$ best solution!! \$\endgroup\$ – LowFieldTheory Dec 7 '19 at 13:34
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @Ranjan Kumar I saw your edit, if you have an improvement to suggest about the code, do this in another answer. I was approaching the style of the code not the content. \$\endgroup\$ – Marc-Andre Mar 16 '15 at 13:55
5
\$\begingroup\$

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);
    }
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ or just return (y - x + d - 1) / d; \$\endgroup\$ – abuzittin gillifirca Apr 10 '14 at 6:51
  • 1
    \$\begingroup\$ I'm seeing this a bit late, but could you add explanation why your solution is better? In it's current state it's nothing more than a code dump. \$\endgroup\$ – Mast Jun 14 '15 at 20:04
  • \$\begingroup\$ I just came here from that test, and your solution is the first one I tried, but it gives me 44%. \$\endgroup\$ – LowFieldTheory Dec 7 '19 at 13:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.