FrogJmp:
Count minimal number of jumps from position X to Y.
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
Write an efficient algorithm for the following assumptions:
- X, Y and D are integers within the range [1..1,000,000,000];
- X ≤ Y.
這題非常簡單，但一開始寫的方式太單純就用了迴圈跑
public static int frogJmp(int x, int y, int d) {
int count = 0;
while (x < y) {
x = x + d;
count++;
}
return count;
}
想當然的效率極差，後來馬上換個方式寫，先算出x和y兩個點的距離，然後再將這個距離除以青蛙跳躍的距離，再判斷是否整除，若有餘數則跳躍次數再加1
public static int frogJmp(int x, int y, int d) {
int range = y - x;
return (range / d) + (range % d != 0 ? 1 : 0);
}
執行結果 : https://app.codility.com/demo/results/trainingBM25NK-BMV/
Cheng® 