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 X 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:

Frog Jump

Python

# Name: FrogJmp # Link: https://codility.com/demo/take-sample-test/frog_jmp/ def solution(X, Y, D): # Calcs the integer part of the division, distance to be traveled by jump size, if the division leaves a rest, add 1 to the result. return ((Y - X)//D) + (1 if (Y - X)%D > 0 else 0)

1 2 3 4 5 6 7

# Name: FrogJmp # Link: https://codility.com/demo/take-sample-test/frog_jmp/     def solution(X, Y, D):     # Calcs the integer part of the division, distance to be traveled by jump size, if the division leaves a rest, add 1 to the result.     return ((Y - X)//D) + (1 if (Y - X)%D > 0 else 0)

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

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