3629. Minimum Jumps to Reach End via Prime Teleportation

Problem Statement (link)

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.

Example 1:

**Input**: nums = [1,2,4,6]
**Output:** 2
**Explanation:**
One optimal sequence of jumps is:
- Start at index `i = 0`. Take an adjacent step to index 1.
- 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.
Thus, the answer is 2.

Example 2:

**Input:** nums = [2,3,4,7,9]
**Output:** 2
**Explanation:**
One optimal sequence of jumps is:
- Start at index `i = 0`. Take an adjacent step to index `i = 1`.
- 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.
Thus, the answer is 2.

Example 3:

**Input:** nums = [4,6,5,8]
**Output:** 3
**Explanation:**
- Since no teleportation is possible, we move through `0 → 1 → 2 → 3`. Thus, the answer is 3.

Constraints:

• 1 <= n == nums.length <= 10^5
• 1 <= nums[i] <= 10^6

Thought process

I need to find the minimum number of jumps to move from the start to the end of the list, it’s an optimization problem and when I find sth like that my head directly trying these techniques and algorithms Optimization problem patterns .

I ignored the DP approach as the size of the array is too large, and start thinking about how to transforming the problem into graph problem specially it looks like there’s a single source index 0 and a single destination the last index.

You may notice that it’s a BFS problem for each index i you may move to index i + 1, i - 1 or any index j such that nums[j] % nums[i] = 0 but that’s only when nums[i] is prime.

But there’s 2 problems:

1. How to check if a number is prime ?
2. How to find as quick as possible the number that are divisible by that prime number ?

Find a number is prime or not is pretty easy Sieve of eratosthenes algorithm, but why not instead of just marking the number as prime or no link the non prime number to their smallest prime factor SPF ??!!!

LIMIT = int(1e6) + 5
 
# calculating primes
is_prime = [True] * LIMIT
spf = [i for i in range(LIMIT)]
is_prime[0] = is_prime[1] = False
 
for i in range(2, math.isqrt(LIMIT) + 1):
	if not is_prime[i]:
		continue
	for itr in range(i + i, LIMIT, i):
		is_prime[itr] = False
		spf[itr] = i

what this code does is that mark a number as prime or not and for each non prime number it set the prime factor to the current prime factor

now for a number like 6 the spf of it is 3, 10 is 5, and 4 is 2 , we can then use these factors to group the numbers from the nums array together under the same prime factor but now 6 is on group 3 while it should be on both 3 and 2.

the second trick comes into play:

groups = defaultdict(set)
for idx, num in enumerate(nums):
	temp = num
	while temp > 1:
		groups[spf[temp]].add(idx)
		temp //= spf[temp]

This loop not just set the number into the direct factor but it loops on it’s dividends until reaching 1 63 (spf = 7) ⇒ 63 // 7 = 9 (spf = 3) ⇒ 9 // 3 = 3 (spf = 3) ⇒ 3 // 3 = 1

so 63 belongs to groups { 7, 3 } so now when there’s 3 or 7 in nums we can easily just to 63 we know that it’s a multiplier for them

class Solution:
	def minJumps(self, nums: list[int]) -> int:
		# ...buiilding groups code
			
		q = deque()
		q.append(0)
		level = 0
		
		visited = set()
		visited_primes = set()
		while q:
			for _ in range(len(q)):
				curr = q.popleft()
				curr_num = nums[curr]
				
				if curr == len(nums) - 1:
					return level
				
				if curr - 1 >= 0 and (curr - 1) not in visited:
					q.append(curr - 1)
					visited.add(curr - 1)
					
				if (curr + 1) not in visited:
					q.append(curr + 1)
					visited.add(curr + 1)
				
				if is_prime[curr_num] and curr_num not in visited_primes:
					for pos in groups[curr_num]:
						if pos not in visited:
							q.append(pos)
							visited.add(pos)
							visited_primes.add(curr_num)
			level += 1
		return level

Complexity

Time: O(MXlogMX)+O(nlogMX) Space: O(MXloglogMX)

Pattern

• single source, single destination
• optimization (minimum, shortest) Then use BFS

New Thing I learn

How to calculate the prime factors of any number using Sieve of eratosthenes