Pages

Codility FrogJmp

You could find the full description of this problem, and check your solution in (possibly) your favorite programming language, on the Codility web site, Time Complexity section. To simply put it, we have to calculate a distance, and determine how many segments of a given size we need to cover that distance.

It is marked as "painless", even if "embarrassingly simple" would probably be a better description. Still, even in this case a mistake could be lurking somewhere, ready to catch us off guard. Here the issue could be that we need to consider two cases, and one of them could be overseen. Here is a couple of test cases (C++, GoogleTest) that clarifies the matter:
TEST(FrogJmp, Given) // 1
{
    ASSERT_EQ(3, solution(10, 85, 30));
}

TEST(FrogJmp, Precise)
{
    ASSERT_EQ(4, solution(10, 90, 20));
}
1. A frog starts its trip on 10, wants to reach 85, and its jump is sized 30. Obviously it needs three steps to get it.
2. A weaker frog on a longer path. In four steps it gets exactly on its end point.

Here is how implemented my solution:
int solution(int x, int y, int d)
{
    assert(x < y); // 1
    assert(d > 0);

    int distance = y - x; // 2
    int steps = distance / d; // 3
    if(distance % d != 0) // 4
        ++steps;
    return steps;
}
1. Assuming no tricky input. The frog starts on the left and goes to the right.
2. This is the distance it has to travel.
3. The solution is just a matter of dividing the distance for the step size ...
4. ... plus one, in case our frog is not lucky enough to drop right on its path end.

2 comments:

  1. Or just return (y - x + d - 1) / d;

    ReplyDelete
    Replies
    1. Beautiful solution in its conciseness, thank you for sharing.

      I liked how you avoided checking the remainder by adding (d-1) before dividing by d. Cool performance-wise trick.

      Delete