Solution to Codility lesson1-exercise2 Frog Jump problem, link to Codility problem and complete solution at the end of the post.
Definitions:
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.
7 |
return ((Y - X)//D) + (1 if (Y - X)%D > 0 else 0) |
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:
12345678
# 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 8 |
# 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)