3629. Minimum Jumps to Reach End via Prime Teleportation Medium

1/**
2 * [3629] Minimum Jumps to Reach End via Prime Teleportation
3 *
4 * You are given an integer array nums of length n.
5 * You start at index 0, and your goal is to reach index n - 1.
6 * From any index i, you may perform one of the following operations:
7 * 
8 * 	Adjacent Step: Jump to index i + 1 or i - 1, if the index is within bounds.
9 * 	Prime Teleportation: If nums[i] is a <span data-keyword="prime-number">prime number</span> p, you may instantly jump to any index j != i such that nums[j] % p == 0.
10 * 
11 * Return the minimum number of jumps required to reach index n - 1.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">nums = [1,2,4,6]</span>
16 * Output: <span class="example-io">2</span>
17 * Explanation:
18 * One optimal sequence of jumps is:
19 * 
20 * 	Start at index i = 0. Take an adjacent step to index 1.
21 * 	At index i = 1, nums[1] = 2 is a prime number. Therefore, we teleport to index i = 3 as nums[3] = 6 is divisible by 2.
22 * 
23 * Thus, the answer is 2.
24 * </div>
25 * <strong class="example">Example 2:
26 * <div class="example-block">
27 * Input: <span class="example-io">nums = [2,3,4,7,9]</span>
28 * Output: <span class="example-io">2</span>
29 * Explanation:
30 * One optimal sequence of jumps is:
31 * 
32 * 	Start at index i = 0. Take an adjacent step to index i = 1.
33 * 	At index i = 1, nums[1] = 3 is a prime number. Therefore, we teleport to index i = 4 since nums[4] = 9 is divisible by 3.
34 * 
35 * Thus, the answer is 2.
36 * </div>
37 * <strong class="example">Example 3:
38 * <div class="example-block">
39 * Input: <span class="example-io">nums = [4,6,5,8]</span>
40 * Output: <span class="example-io">3</span>
41 * Explanation:
42 * 
43 * 	Since no teleportation is possible, we move through 0 &rarr; 1 &rarr; 2 &rarr; 3. Thus, the answer is 3.
44 * </div>
45 *  
46 * Constraints:
47 * 
48 * 	1 <= n == nums.length <= 10^5
49 * 	1 <= nums[i] <= 10^6
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/minimum-jumps-to-reach-end-via-prime-teleportation/
55// discuss: https://leetcode.com/problems/minimum-jumps-to-reach-end-via-prime-teleportation/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn min_jumps(nums: Vec<i32>) -> i32 {
61        0
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_3629() {
73    }
74}
75