Package g1601_1700.s1654_minimum_jumps_to_reach_home

Class Solution

java.lang.Object

g1601_1700.s1654_minimum_jumps_to_reach_home.Solution

public class Solution
extends Object

1654 - Minimum Jumps to Reach Home.<p>Medium</p> <p>A certain bug&rsquo;s home is on the x-axis at position <code>x</code>. Help them get there from position <code>0</code>.</p> <p>The bug jumps according to the following rules:</p> <ul> <li>It can jump exactly <code>a</code> positions <strong>forward</strong> (to the right).</li> <li>It can jump exactly <code>b</code> positions <strong>backward</strong> (to the left).</li> <li>It cannot jump backward twice in a row.</li> <li>It cannot jump to any <code>forbidden</code> positions.</li> </ul> <p>The bug may jump forward <strong>beyond</strong> its home, but it <strong>cannot jump</strong> to positions numbered with <strong>negative</strong> integers.</p> <p>Given an array of integers <code>forbidden</code>, where <code>forbidden[i]</code> means that the bug cannot jump to the position <code>forbidden[i]</code>, and integers <code>a</code>, <code>b</code>, and <code>x</code>, return <em>the minimum number of jumps needed for the bug to reach its home</em>. If there is no possible sequence of jumps that lands the bug on position <code>x</code>, return <code>-1.</code></p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11</p> <p><strong>Output:</strong> -1</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= forbidden.length <= 1000</code></li> <li><code>1 <= a, b, forbidden[i] <= 2000</code></li> <li><code>0 <= x <= 2000</code></li> <li>All the elements in <code>forbidden</code> are distinct.</li> <li>Position <code>x</code> is not forbidden.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minimumJumps(int[] forbidden, int a, int b, int x)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

minimumJumps

public int minimumJumps(int[] forbidden,
 int a,
 int b,
 int x)