Problem Statement |
| | Rabbits often feel lonely, so when they go out to meet their friends, they jump as quickly as possible.
Rabbit Iris is on an infinitely long straight road. Points on this road are numbered ..., -3, -2, -1, 0, 1, 2, 3, ... from west to east. Iris is at point 0 now, and she is going to meet her friend at point 1,000,000,001. She can only move by jumping, and she can perform two types of jumps: small and large. When she is at point x,
- By making a small jump, she can move to either point (x + 2) or point (x - 2).
- By making a large jump, she can move to either point (x + largeJump) or point (x - largeJump).
Unfortunately, the road contains holes, and Iris can never land on a point which contains a hole. You are given a int[] holes containing N * 2 elements. For each i, where 0 <= i < N, all points between holes[i * 2] and holes[i * 2 + 1], inclusive, contain holes.
Iris prefers to perform small jumps because she can do them faster. Return the minimum number of large jumps required to reach point 1,000,000,001. If it is impossible to reach that point, return -1 instead. |
| |
Definition |
| | | Class: | RabbitJumping | | Method: | getMinimum | | Parameters: | int[], int | | Returns: | int | | Method signature: | int getMinimum(int[] holes, int largeJump) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Iris can travel to points with negative numbers and numbers greater than 1,000,000,001. |
| |
Constraints |
| - | holes will contain between 2 and 50 elements, inclusive. |
| - | holes will contain an even number of elements. |
| - | Each element of holes will be between 1 and 1,000,000,000, inclusive. |
| - | Elements of holes will be in strictly increasing order. |
| - | largeJump will be between 3 and 1,000,000,000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 1 | 0 => 3 -> 5 -> 7 -> ... -> 999999999 -> 1000000001
Iris needs to make at least one large jump to jump over the holes at points 1 and 2. |
|
|
| 1) | |
| | | Returns: -1 | | Iris can never step on point 1,000,000,001, or any other odd-numbered point.
|
|
|
| 2) | |
| | | Returns: 3 | One solution to reach the goal with 3 large jumps is:
0 -> -2 => 1 => 4 => 7 -> 9 -> 11 -> ... -> 999999999 -> 1000000001
|
|
|
| 3) | |
| | { 2, 17, 21, 36, 40, 55, 59, 74 } | 19 |
| Returns: 5 | |
|
| 4) | |
| | { 187640193, 187640493, 187640738, 187640845, 564588641, 564588679,
564588696, 564588907, 605671187, 605671278, 605671288, 605671386,
755723729, 755723774, 755723880, 755723920, 795077469, 795077625,
795077851, 795078039, 945654724, 945654815, 945655107, 945655323 }
| 475 |
| Returns: 9 | |
|