Minimum Jumps to Reach End via Prime Teleportation
You are given an integer array nums of length n.
You start at index 0, and your goal is to reach index n - 1.
From any index i, you may perform one of the following operations:
- Adjacent Step: Jump to index
i + 1ori - 1, if the index is within bounds. - Prime Teleportation: If
nums[i]is a prime numberp, you may instantly jump to any indexj != isuch thatnums[j] % p == 0.
Return the minimum number of jumps required to reach index n - 1.
Example 1
Input
nums = [1,2,4,6]Output
2One optimal sequence is to step from index 0 to index 1, then teleport from prime value 2 to index 3 because 6 is divisible by 2.
Example 2
Input
nums = [2,3,4,7,9]Output
2One optimal sequence is to step from index 0 to index 1, then teleport from prime value 3 to index 4 because 9 is divisible by 3.
Constraints
- 1 <= n == nums.length <= 10^5
- 1 <= nums[i] <= 10^6