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:
i + 1 or i - 1, if the index is within bounds.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.
Example 1:
Input: nums = [1,2,4,6]
Output: 2
Explanation:
One optimal sequence of jumps is:
i = 0. Take an adjacent step to index 1.i = 1, nums[1] = 2 is a prime number. Therefore, we teleport to index i = 3 as nums[3] = 6 is divisible by 2.Thus, the answer is 2.
Example 2:
Input: nums = [2,3,4,7,9]
Output: 2
Explanation:
One optimal sequence of jumps is:
i = 0. Take an adjacent step to index i = 1.i = 1, nums[1] = 3 is a prime number. Therefore, we teleport to index i = 4 since nums[4] = 9 is divisible by 3.Thus, the answer is 2.
Example 3:
Input: nums = [4,6,5,8]
Output: 3
Explanation:
0 → 1 → 2 → 3. Thus, the answer is 3.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 106Problem Overview: You start at index 0 of an array and want to reach the last index using the minimum number of jumps. Besides moving to adjacent indices, certain numbers allow prime-based teleportation, creating additional edges between positions that share prime factors.
Approach 1: Brute Force BFS with Pairwise Prime Check (O(n² log V) time, O(n) space)
Treat the array as an implicit graph where each index is a node. From index i, you can move to i-1, i+1, or any index whose value shares a prime factor with nums[i]. A straightforward solution runs Breadth-First Search and checks every other element to see if they share a prime factor using repeated factorization or gcd. BFS guarantees the first time you reach the last index is the minimum number of jumps. The downside is the repeated pairwise checks, which lead to O(n² log V) complexity in the worst case.
Approach 2: BFS with Prime Factor Hash Mapping (O(n log V) time, O(n + P) space)
The optimized solution avoids scanning the entire array for teleport candidates. First compute the prime factors for every value using basic number factorization or a sieve from Number Theory. Build a hash map from each prime factor to the list of indices containing that factor. During BFS, when you visit index i, iterate through the prime factors of nums[i] and instantly retrieve all indices connected through that prime using a hash table. Push those indices into the BFS queue and then clear the list for that prime so it is processed only once. This prevents repeated traversals and keeps the total work close to linear.
The BFS queue stores (index, steps). Each expansion adds neighbors i-1, i+1, and all teleport indices discovered from the prime map. A visited array prevents revisiting nodes. Clearing processed prime groups ensures each teleport edge is used only once, which is the key optimization.
Recommended for interviews: The BFS with prime-factor hashing is the expected solution. It demonstrates graph modeling, number factorization, and careful pruning to keep the complexity near O(n log V). Explaining the brute force approach first shows understanding of the graph structure, while the optimized version shows the ability to reduce redundant work using hashing and number theory.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force BFS with Pairwise Prime Check | O(n² log V) | O(n) | Useful for understanding the graph structure or when constraints are very small |
| BFS with Prime Factor Hash Mapping | O(n log V) | O(n + P) | General case. Efficient for large arrays by grouping indices by prime factors |
| BFS with Sieve Precomputation | O(n log V) | O(n + V) | Best when values are large and repeated factorization becomes expensive |
LeetCode 3629. Minimum Jumps to Reach End via Prime Teleportation | Shortest distance | Dijkstra • Leet's Code • 629 views views
Watch 8 more video solutions →Practice Minimum Jumps to Reach End via Prime Teleportation with our built-in code editor and test cases.
Practice on FleetCode