FastPrep
Problem · Dynamic Programming

Jump Game with Prime-Step Rule

● MediumUberFULLTIMEOA
See Uber hiring insights

You are given an integer array nums. You start at index 0 and want to reach index n - 1.

From index i, you may jump to any later index j if the step length j - i is prime and j - i <= nums[i].

Return 1 if the last index is reachable, otherwise return 0.

Function Description

Complete the function canReachWithPrimeSteps in the editor below.

canReachWithPrimeSteps has the following parameter:

  1. int[] nums: the maximum jump lengths

Returns

int: 1 if the end is reachable, otherwise 0.

Examples
01 · Example 1
nums = [2, 3, 1, 1, 0]
return = 0
From index 0 (nums[0]=2), the only valid prime step is 2, reaching index 2. From index 2 (nums[2]=1), no prime step is possible because the minimum prime is 2 but nums[2]=1 < 2. No path reaches the last index, so the answer is 0.
02 · Example 2
nums = [1, 1, 1, 1]
return = 0

Every allowed jump length is at most 1, and 1 is not prime.

Constraints
  • 1 <= nums.length <= 2 * 10^5
  • 0 <= nums[i] <= 10^9
More Uber problems
drafts saved locally
public int canReachWithPrimeSteps(int[] nums) {
    // write your code here
}
nums[2, 3, 1, 1, 0]
expected0
sign in to submit