#3629
Minimum Jumps to Reach End via Prime Teleportation
medium · 31.8% accepted · 130 likes · top 9%
array · hash table · math · breadth-first search · number theory
Description
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 + 1 or i - 1, if the index is within bounds.
- Prime Teleportation: If nums[i] is a prime number p, you may instantly jump to any index j != i such that nums[j] % p == 0.
Return the minimum number of jumps required to reach index n - 1.
Solution