Minimum Jumps to Reach End via Prime Teleportation
Problem
You start at index 0 of an array nums of length n and want to reach index n − 1 in as few jumps as possible. From index i you can take an adjacent step to i + 1 or i − 1 (if in bounds). And if nums[i] is a prime p, you may teleport to any index j ≠ i with nums[j] % p == 0. Return the minimum number of jumps.
nums = [1, 2, 4, 6]2def minJumps(nums):
n = len(nums)
if n == 1:
return 0
mx = max(nums)
spf = list(range(mx + 1)) # smallest prime factor sieve
i = 2
while i * i <= mx:
if spf[i] == i: # i is prime
for j in range(i * i, mx + 1, i):
if spf[j] == j:
spf[j] = i
i += 1
# bucket[p] = indices j with nums[j] % p == 0
bucket = {}
for j, v in enumerate(nums):
x = v
while x > 1: # distinct prime factors of v
p = spf[x]
bucket.setdefault(p, []).append(j)
while x % p == 0:
x //= p
dist = [-1] * n
dist[0] = 0
queue = [0]
while queue:
i = queue.pop(0)
if i == n - 1:
return dist[i]
for nb in (i - 1, i + 1): # adjacent steps
if 0 <= nb < n and dist[nb] == -1:
dist[nb] = dist[i] + 1
queue.append(nb)
p = nums[i]
if spf[p] == p and p > 1 and p in bucket: # nums[i] is prime
for nb in bucket[p]: # teleport to every multiple of p
if dist[nb] == -1:
dist[nb] = dist[i] + 1
queue.append(nb)
del bucket[p] # visit each prime bucket once
return dist[n - 1]function minJumps(nums) {
const n = nums.length;
if (n === 1) return 0;
const mx = Math.max(...nums);
const spf = Array.from({ length: mx + 1 }, (_, k) => k); // smallest prime factor
for (let i = 2; i * i <= mx; i++) {
if (spf[i] === i) { // i is prime
for (let j = i * i; j <= mx; j += i) {
if (spf[j] === j) spf[j] = i;
}
}
}
// bucket[p] = indices j with nums[j] % p === 0
const bucket = new Map();
for (let j = 0; j < n; j++) {
let x = nums[j];
while (x > 1) { // distinct prime factors
const p = spf[x];
if (!bucket.has(p)) bucket.set(p, []);
bucket.get(p).push(j);
while (x % p === 0) x = Math.floor(x / p);
}
}
const dist = new Array(n).fill(-1);
dist[0] = 0;
const queue = [0];
let head = 0;
while (head < queue.length) {
const i = queue[head++];
if (i === n - 1) return dist[i];
for (const nb of [i - 1, i + 1]) { // adjacent steps
if (nb >= 0 && nb < n && dist[nb] === -1) {
dist[nb] = dist[i] + 1;
queue.push(nb);
}
}
const p = nums[i];
if (spf[p] === p && p > 1 && bucket.has(p)) { // nums[i] is prime
for (const nb of bucket.get(p)) { // teleport to each multiple
if (dist[nb] === -1) {
dist[nb] = dist[i] + 1;
queue.push(nb);
}
}
bucket.delete(p); // visit each bucket once
}
}
return dist[n - 1];
}int minJumps(int[] nums) {
int n = nums.length;
if (n == 1) return 0;
int mx = 0;
for (int v : nums) mx = Math.max(mx, v);
int[] spf = new int[mx + 1]; // smallest prime factor sieve
for (int k = 0; k <= mx; k++) spf[k] = k;
for (int i = 2; (long) i * i <= mx; i++) {
if (spf[i] == i) { // i is prime
for (int j = i * i; j <= mx; j += i)
if (spf[j] == j) spf[j] = i;
}
}
// bucket[p] = indices j with nums[j] % p == 0
Map<Integer, List<Integer>> bucket = new HashMap<>();
for (int j = 0; j < n; j++) {
int x = nums[j];
while (x > 1) { // distinct prime factors
int p = spf[x];
bucket.computeIfAbsent(p, z -> new ArrayList<>()).add(j);
while (x % p == 0) x /= p;
}
}
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[0] = 0;
Deque<Integer> queue = new ArrayDeque<>();
queue.add(0);
while (!queue.isEmpty()) {
int i = queue.poll();
if (i == n - 1) return dist[i];
for (int nb : new int[]{i - 1, i + 1}) { // adjacent steps
if (nb >= 0 && nb < n && dist[nb] == -1) {
dist[nb] = dist[i] + 1;
queue.add(nb);
}
}
int p = nums[i];
if (spf[p] == p && p > 1 && bucket.containsKey(p)) { // prime
for (int nb : bucket.get(p)) { // teleport
if (dist[nb] == -1) {
dist[nb] = dist[i] + 1;
queue.add(nb);
}
}
bucket.remove(p); // visit each bucket once
}
}
return dist[n - 1];
}int minJumps(vector<int>& nums) {
int n = nums.size();
if (n == 1) return 0;
int mx = *max_element(nums.begin(), nums.end());
vector<int> spf(mx + 1); // smallest prime factor sieve
for (int k = 0; k <= mx; k++) spf[k] = k;
for (int i = 2; (long long) i * i <= mx; i++) {
if (spf[i] == i) { // i is prime
for (int j = i * i; j <= mx; j += i)
if (spf[j] == j) spf[j] = i;
}
}
// bucket[p] = indices j with nums[j] % p == 0
unordered_map<int, vector<int>> bucket;
for (int j = 0; j < n; j++) {
int x = nums[j];
while (x > 1) { // distinct prime factors
int p = spf[x];
bucket[p].push_back(j);
while (x % p == 0) x /= p;
}
}
vector<int> dist(n, -1);
dist[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty()) {
int i = q.front(); q.pop();
if (i == n - 1) return dist[i];
for (int nb : {i - 1, i + 1}) { // adjacent steps
if (nb >= 0 && nb < n && dist[nb] == -1) {
dist[nb] = dist[i] + 1;
q.push(nb);
}
}
int p = nums[i];
if (spf[p] == p && p > 1 && bucket.count(p)) { // prime
for (int nb : bucket[p]) { // teleport
if (dist[nb] == -1) {
dist[nb] = dist[i] + 1;
q.push(nb);
}
}
bucket.erase(p); // visit each bucket once
}
}
return dist[n - 1];
}Explanation
Every jump has the same cost (one move), so the minimum number of jumps is just the shortest path in an unweighted graph where nodes are indices. That makes this a classic breadth-first search (BFS): the first time BFS reaches index n − 1, the distance recorded is the answer.
The tricky part is the edges. Adjacent steps are easy: index i connects to i − 1 and i + 1. The prime teleport adds many more edges: if nums[i] is a prime p, then i connects to every index j whose value is a multiple of p. Materialising all those edges explicitly would be far too many.
The fix is a bucket keyed by prime. We factor each value with a smallest-prime-factor sieve and, for every distinct prime p dividing nums[j], append j to bucket[p]. During BFS, when we sit on a prime value p, we visit the whole bucket[p] at once and then delete that bucket. Clearing it guarantees each prime's group of multiples is expanded only one time across the entire search, which keeps the work linear overall instead of quadratic.
Why is deleting safe? BFS visits nodes in non-decreasing distance order. The first index that lands on prime p already offers the cheapest entry point into the whole bucket, so any later index on the same prime cannot improve those distances — the bucket has nothing new to give.
Example nums = [1, 2, 4, 6]: BFS starts at index 0 (distance 0), steps to index 1 (distance 1). At index 1 the value 2 is prime, so it teleports across bucket[2] = [1, 2, 3], reaching index 3 at distance 2 — the destination. The answer is 2.