Minimum Jumps to Reach End via Prime Teleportation

What the problem is really asking

We are standing on index 0, and every move costs 1.

From an index, we can always try the adjacent positions. Sometimes we also get a shortcut: if the current value is a prime p, we can jump to any index whose value is divisible by p.

So this is a shortest path problem on array indices. The natural tool is BFS.

Key Idea

The expensive part is teleportation.

If we are at a prime value p, we need all indices j where:

nums[j] % p == 0

Scanning the whole array every time we stand on a prime would be too slow.

Instead, preprocess buckets by prime factor:

prime p -> all indices whose value is divisible by p

Then when BFS reaches a prime value p, the bucket for p is exactly the teleport list.

Preprocessing

Use a sieve to build the smallest prime factor for every value up to max(nums).

Then for every nums[i], factor it into unique prime factors. For each unique factor p, add index i into edges[p].

Unique factors matter because a value like 12 should enter bucket 2 only once:

12 = 2 * 2 * 3
unique prime factors = 2, 3

BFS

Start BFS from index 0.

For each popped index:

1. Try index - 1.
2. Try index + 1.
3. If nums[index] is prime, consume its teleport bucket.

After a prime bucket is used once, delete it.

That deletion is important. If we do not remove it, many prime positions with the same value can rescan the same long list again and again.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

class Solution {
    public int minJumps(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 0;
        }

        int maxValue = 1;
        for (int num : nums) {
            maxValue = Math.max(maxValue, num);
        }

        int[] spf = buildSmallestPrimeFactor(maxValue);
        Map<Integer, List<Integer>> edges = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int value = nums[i];

            while (value > 1) {
                int prime = spf[value];
                edges.computeIfAbsent(prime, key -> new ArrayList<>()).add(i);

                while (value % prime == 0) {
                    value /= prime;
                }
            }
        }

        boolean[] seen = new boolean[n];
        Queue<Integer> queue = new ArrayDeque<>();
        seen[0] = true;
        queue.offer(0);
        int jumps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int step = 0; step < size; step++) {
                int index = queue.poll();

                if (index == n - 1) {
                    return jumps;
                }

                if (index > 0 && !seen[index - 1]) {
                    seen[index - 1] = true;
                    queue.offer(index - 1);
                }

                if (index + 1 < n && !seen[index + 1]) {
                    seen[index + 1] = true;
                    queue.offer(index + 1);
                }

                int value = nums[index];
                if (value >= 2 && spf[value] == value) {
                    List<Integer> targets = edges.remove(value);

                    if (targets != null) {
                        for (int next : targets) {
                            if (!seen[next]) {
                                seen[next] = true;
                                queue.offer(next);
                            }
                        }
                    }
                }
            }

            jumps++;
        }

        return -1;
    }

    private int[] buildSmallestPrimeFactor(int maxValue) {
        int[] spf = new int[maxValue + 1];

        for (int i = 2; i <= maxValue; i++) {
            if (spf[i] != 0) {
                continue;
            }

            spf[i] = i;

            if ((long) i * i > maxValue) {
                continue;
            }

            for (long j = (long) i * i; j <= maxValue; j += i) {
                if (spf[(int) j] == 0) {
                    spf[(int) j] = i;
                }
            }
        }

        return spf;
    }
}

Dry Run

Take:

nums = [1, 2, 4, 6]

The buckets are:

2 -> indices [1, 2, 3]
3 -> indices [3]

BFS starts at index 0.

Distance 0

At index 0, we can only move to index 1.

Distance 1

At index 1, nums[1] = 2, which is prime.

So we can teleport to every index in bucket 2. That reaches index 3, the final index.

The answer is 2.

Why deleting a bucket is safe

BFS processes states in increasing distance.

The first time we use teleport bucket p, we are using it from the earliest possible prime index with value p. Every target in that bucket gets its best possible distance from this teleport.

If another index with the same prime value appears later, using the same bucket again cannot improve any distance. So removing the bucket keeps the work linear without changing the answer.

Common mistakes

1. Teleporting from non-prime values

Only prime current values can start teleportation.

For example, from value 4, we cannot teleport using prime factor 2.

2. Scanning all indices for every prime

That can become O(n^2). Use prime-factor buckets instead.

3. Adding duplicate factors

When factorizing 12, add it to bucket 2 once and bucket 3 once. Do not add it twice to bucket 2.

Complexity

Let n be the length of nums, and let MX = max(nums).

• Time complexity: O(MX log log MX + n log MX)
• Space complexity: O(MX + n log MX)

The sieve builds smallest prime factors. Each index is visited once in BFS, and each prime bucket is consumed at most once.

Final Takeaway

Model the array as a graph and run BFS.

The trick is not BFS itself, but making teleport edges cheap: group indices by prime factor, then clear each teleport bucket after the first use.