FastPrep
Problem · Dynamic Programming

Jump Game with Prime-Step Rule

Learn this problem
● MediumUber logoUberFULLTIMEOA
See Uber hiring insights

Problem statement

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

canReachWithPrimeSteps(nums: int[]) → int

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

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.

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
checking account