LeetCode 3629 - Minimum Jumps to Reach End via Prime Teleportation
This problem is essentially about navigating an array using two types of moves: adjacent steps and prime-based teleportation. You start at the first index and want to reach the last index in the minimum number of moves.
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Breadth-First Search, Number Theory
Solution
Problem Understanding
This problem is essentially about navigating an array using two types of moves: adjacent steps and prime-based teleportation. You start at the first index and want to reach the last index in the minimum number of moves. An adjacent step is straightforward: you can move to the next or previous index if it exists. The twist is the prime teleportation: if the number at your current index is prime, you can jump to any other index whose number is divisible by this prime.
The input nums is an array of integers, with a length up to 10^5 and values up to 10^6. The output is a single integer representing the minimum number of jumps required to reach the end. The constraints imply that a naive brute-force approach that considers all teleportation possibilities repeatedly will be too slow. Edge cases to consider include arrays with no primes, arrays where every number is prime, small arrays (length 1 or 2), and cases where teleportation offers a significant shortcut.
Approaches
The brute-force approach would be to model the problem as a graph where each index is a node, and edges connect indices via adjacent steps or valid prime teleportation. You could perform a BFS, exploring all possibilities. While BFS guarantees finding the shortest path, generating all teleportation edges is costly because, for each prime, you would need to check every other index for divisibility. This could result in O(n^2) operations in the worst case, which is infeasible for n up to 100,000.
The optimal approach leverages the observation that prime teleportation edges can be preprocessed. Instead of checking divisibility on the fly, we create a mapping from each prime to the list of indices divisible by it. We perform a BFS starting from index 0. For each visited index, we first consider adjacent steps. If the number at the index is prime, we look up all indices divisible by it and add them to the BFS queue. Once we use a prime for teleportation, we mark it as used to avoid revisiting the same set of indices. This preprocessing reduces redundant checks and ensures that each teleportation set is only used once.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) | BFS with naive teleportation checks |
| Optimal | O(n * log log M + n) | O(n + M) | BFS with preprocessed prime-to-index mapping (M = max(nums)) |
Algorithm Walkthrough
- Precompute primes up to max(nums): Use the Sieve of Eratosthenes to generate a list of primes up to the maximum number in
nums. This allows for fast prime checks and factorization. - Build a prime-to-indices mapping: Iterate over the array. For each index, factorize
nums[i]into primes. For each prime factor, append the current index to a dictionary mapping that prime to all indices divisible by it. This enables O(1) access to teleport destinations. - Initialize BFS: Start from index 0, with a queue storing
(index, jumps). Also, maintain avisitedset to prevent revisiting indices. - BFS traversal:
- Dequeue
(i, jumps). - If
iequalsn-1, returnjumps. - Consider adjacent steps: if
i+1ori-1is in bounds and unvisited, enqueue withjumps+1and mark as visited. - Consider prime teleportation: factorize
nums[i]to get its prime factors. For each prime factorp, if we have not yet used it, enqueue all indices mapped top(excluding visited), mark them visited, and mark primepas used. This ensures each teleportation group is used once.
- Termination: BFS guarantees the first time we reach
n-1is the minimum number of jumps because each level represents one jump.
Why it works: BFS ensures minimal steps because each level explores all nodes reachable in that many jumps. Using the prime-to-index mapping avoids redundant teleportation checks and prevents infinite loops by marking primes as used.
Python Solution
from collections import deque, defaultdict
from math import isqrt
from typing import List
class Solution:
def minJumps(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
# Helper: Sieve of Eratosthenes to find primes up to max(nums)
def sieve(max_val):
is_prime = [True] * (max_val + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, isqrt(max_val) + 1):
if is_prime[i]:
for j in range(i*i, max_val+1, i):
is_prime[j] = False
return is_prime
max_num = max(nums)
is_prime_arr = sieve(max_num)
# Build prime to indices mapping
prime_to_indices = defaultdict(list)
for idx, num in enumerate(nums):
val = num
for p in range(2, isqrt(val)+1):
if val % p == 0:
if is_prime_arr[p]:
prime_to_indices[p].append(idx)
while val % p == 0:
val //= p
if val > 1 and is_prime_arr[val]:
prime_to_indices[val].append(idx)
visited = [False] * n
visited[0] = True
used_primes = set()
queue = deque([(0, 0)])
while queue:
idx, jumps = queue.popleft()
if idx == n - 1:
return jumps
# Adjacent steps
for nei in [idx-1, idx+1]:
if 0 <= nei < n and not visited[nei]:
visited[nei] = True
queue.append((nei, jumps+1))
# Prime teleportation
val = nums[idx]
primes = set()
tmp = val
for p in range(2, isqrt(tmp)+1):
if tmp % p == 0 and is_prime_arr[p]:
primes.add(p)
while tmp % p == 0:
tmp //= p
if tmp > 1 and is_prime_arr[tmp]:
primes.add(tmp)
for p in primes:
if p in used_primes:
continue
for dest in prime_to_indices[p]:
if not visited[dest]:
visited[dest] = True
queue.append((dest, jumps+1))
used_primes.add(p)
return -1
Implementation Walkthrough: We first generate primes up to the largest number to enable quick factorization. Then we map primes to all divisible indices. BFS explores all possible moves level by level. Adjacent moves are straightforward. For teleportation, we factor the current number and check if its prime factors have been used; if not, we enqueue all corresponding indices. This ensures minimal jumps are discovered.
Go Solution
package main
import (
"math"
)
func minJumps(nums []int) int {
n := len(nums)
if n == 1 {
return 0
}
maxNum := 0
for _, num := range nums {
if num > maxNum {
maxNum = num
}
}
// Sieve of Eratosthenes
isPrime := make([]bool, maxNum+1)
for i := 2; i <= maxNum; i++ {
isPrime[i] = true
}
for i := 2; i*i <= maxNum; i++ {
if isPrime[i] {
for j := i * i; j <= maxNum; j += i {
isPrime[j] = false
}
}
}
// Build prime -> indices map
primeToIndices := map[int][]int{}
for idx, val := range nums {
tmp := val
for p := 2; p*p <= tmp; p++ {
if tmp%p == 0 && isPrime[p] {
primeToIndices[p] = append(primeToIndices[p], idx)
for tmp%p == 0 {
tmp /= p
}
}
}
if tmp > 1 && isPrime[tmp] {
primeToIndices[tmp] = append(primeToIndices[tmp], idx)
}
}
visited := make([]bool, n)
visited[0] = true
usedPrimes := map[int]bool{}
type pair struct{ idx, jumps int }
queue := []pair{{0, 0}}
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
idx, jumps := curr.idx, curr.jumps
if idx == n-1 {
return jumps
}
for _, nei := range []int{idx - 1, idx + 1} {
if nei >= 0 && nei < n && !visited[nei] {
visited[nei] = true
queue = append(queue, pair{nei, jumps + 1})
}
}
// Prime teleportation
tmp := nums[idx]
primes := map[int]bool{}
for p := 2; p*p <= tmp; p++