Codility - Frog Jump

Solution to Codility lesson1-exercise2 Frog Jump problem, link to Codility problem and complete solution at the end of the post.

Definitions:
\{X, Y, D \in \mathbb{N}\ |\ 1\leq X, Y, D\leq 1,000,000,000 \land X \leq Y \}

Problem:
Define a function solution with input X, Y, D, such that solution returns the minimum number of jumps needed to reach a position equal or greater than Y from position X, being D the distance traveled in each jump.

  • Expected worst-case time complexity is O(1);
  • Expected worst-case space complexity is O(1);

Analysis:

To solve this one, we must establish the distance to be traveled, which is (Y - X). This distance divided by D will give us the exact number of jumps to travel from to Y. But, since the frog can't jump in fractions, the result of this solution will be the ceiling of the float division (Y - X)/D. Without the use of python math.ceil() function, this can be achieved with the follow line of code.

Since we do only a few operations regardless the size of our input, the solution time complexity is O(1), the same goes to the space complexity.

Complete Solution:

Time Complexity O(1)
Space Complexity O(1)

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/