Reach the Last Index with Prime Jumps

# Reach the Last Index with Prime Jumps You are given an integer array `nums` of length `n`. Start at index `0` and reach index `n - 1` using as few jumps as possible. From index `i`, one jump may be either: - An **adjacent step** to `i - 1` or `i + 1`, provided that index is in the array. - A **prime teleport**: if `nums[i]` itself is a prime number `p`, jump to any different index `j` whose value is divisible by `p`. Return the minimum number of jumps. Each adjacent step or teleport counts as one jump. ### C++ Interface ```cpp class Solution { public: int minJumps(vector<int>& nums) { } }; ``` ### Examples **Example 1** **Input:** `nums = [6, 2, 9, 15, 10]` **Output:** `2` **Explanation:** Move from index `0` to index `1`, then teleport from value `2` to index `4`, whose value is `10`. A single jump cannot reach index `4`: the starting value `6` is composite, and an adjacent step reaches only index `1`. **Example 2** **Input:** `nums = [3, 1, 8, 6, 5, 4, 10]` **Output:** `3` **Explanation:** Use indices `0 -> 3 -> 4 -> 6`. The first teleport is allowed because `6` is divisible by `3`; the last is allowed because `10` is divisible by `5`. After one jump, only indices `1` and `3` can have been reached. Neither can reach index `6` in one more jump, so two jumps are insufficient. ### Constraints - `1 <= n == nums.length <= 100000` - `1 <= nums[i] <= 1000000` ### Clarifying Questions - Is `1` prime? No. A composite value also cannot initiate a teleport, even if it has prime factors. - Can a teleport go backward? Yes; the destination may be any different valid index satisfying the divisibility rule. - What if the array has one element? You are already at the destination, so return `0`. ### What a Strong Answer Covers - A minimum-jump count that respects both move rules and the prime-value eligibility condition. - Correct handling of repeated values, value `1`, and a one-element array. - A time and space analysis appropriate for the full input bounds. ### Follow-up Questions - How would the return contract change if one shortest route were also required? - What would change in the problem specification if the start and destination indices were supplied separately? ```hint Group eligible destinations Treat each jump as a unit-cost edge. A breadth-first search can use prime-divisor buckets for destinations, but a bucket may be expanded only from a position whose value is that prime. Consider why its destinations need to be scanned only once. ```