#3629
Minimum Jumps to Reach End via Prime Teleportation
MediumArrayHash TableMathBreadth-First SearchNumber TheoryHash MapArray
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
Using BFS allows us to explore the shortest path efficiently. By precomputing prime factors, we can quickly find teleportation options.
⚙️
Algorithm
3 steps- 1Step 1: Precompute prime factors for each number in nums using a sieve method.
- 2Step 2: Create a bucket mapping each prime to indices where nums[j] % prime == 0.
- 3Step 3: Use BFS to explore jumps, considering both adjacent steps and teleportation via primes.
solution.py26 lines
1from collections import deque, defaultdict
2import sympy
3
4def minJumps(nums):
5 n = len(nums)
6 if n <= 1: return 0
7 prime_map = defaultdict(list)
8 for i in range(n):
9 for p in sympy.primerange(2, nums[i] + 1):
10 if nums[i] % p == 0:
11 prime_map[p].append(i)
12 queue = deque([(0, 0)])
13 visited = set([0])
14 while queue:
15 index, jumps = queue.popleft()
16 if index == n - 1: return jumps
17 for step in [1, -1]:
18 if 0 <= index + step < n and (index + step) not in visited:
19 visited.add(index + step)
20 queue.append((index + step, jumps + 1))
21 for p in sympy.primerange(2, nums[index] + 1):
22 for j in prime_map[p]:
23 if j != index and j not in visited:
24 visited.add(j)
25 queue.append((j, jumps + 1))
26 del prime_map[p]ℹ
Complexity note: BFS explores each node once, and precomputation of primes is linear with respect to n.
- 1Understanding prime factorization helps optimize jumps.
- 2BFS is effective for shortest path problems.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.