Minimum Jumps to Reach End via Prime Teleportation

May 8th, 2026

Description

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⁵
1 <= nums[i] <= 10⁶

Solutions

Solution 5 takes a fundamentally different approach by precomputing all prime factors for every number up to 1,000,000 in a factors array. It then uses BFS where from each position you can jump to adjacent indices or to any position whose value shares a prime factor. It further optimizes by using an edges map to track which positions have each factor and clearing processed factors to ensure each connection is explored only once, making it highly efficient.

Language: javascript(2026-05-08 10:14)DONE

CPU Performance22.22%

Memory Performance11.11%

const MX = 1_000_000;
const factors = Array.from({ length: MX + 1 }, () => []);

for (let i = 2; i <= MX; i++) {
    if (factors[i].length === 0) {
        for (let j = i; j <= MX; j += i) {
            factors[j].push(i);
        }
    }
}

var minJumps = function (nums) {
    const n = nums.length;
    const edges = new Map();

    for (let i = 0; i < n; i++) {
        for (const p of factors[nums[i]]) {
            if (!edges.has(p)) edges.set(p, []);
            edges.get(p).push(i);
        }
    }

    const seen = new Array(n).fill(false);
    seen[0] = true;
    let q = [0];
    let res = 0;

    while (true) {
        let q2 = [];

        for (const i of q) {
            if (i === n - 1) return res;

            if (i > 0 && !seen[i - 1]) {
                seen[i - 1] = true;
                q2.push(i - 1);
            }
            if (i < n - 1 && !seen[i + 1]) {
                seen[i + 1] = true;
                q2.push(i + 1);
            }

            if (factors[nums[i]].length === 1) {
                const p = nums[i];
                const list = edges.get(p);

                if (list && list.length > 0) {
                    for (const j of list) {
                        if (!seen[j]) {
                            seen[j] = true;
                            q2.push(j);
                        }
                    }

                    edges.set(p, []);
                }
            }
        }

        q = q2;
        res++;
    }

    return -1;
};