Skip to content

3629. Minimum Jumps to Reach End via Prime Teleportation

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 <= 105
  • 1 <= nums[i] <= 106

Solutions

Solution 1: Preprocessing + BFS

Thinking

From \(i\) we may step to a neighbor or teleport to every \(j\) whose value is divisible by a prime factor of \(\textit{nums}[i]\). The shortest path is an unweighted BFS.

Scanning the whole array on every teleport would explode. Precompute prime factors and, for each prime \(p\), the list \(g[p]\) of indices whose value is a multiple of \(p\).

BFS expands \(i\pm 1\) and \(g[\textit{nums}[i]]\), then clears that list so each prime is used once. The BFS layer that first reaches \(n-1\) is the answer.

First, we preprocess the list of prime factors for every number up to \(10^6\) and store them in \(\textit{factors}\).

Then we build a graph \(g\). For each index \(i\) and each \(p \in \textit{factors}[nums[i]]\), we add \(i\) to \(g[p]\). In this way, we obtain the list of indices that can be reached by teleportation through each prime number \(p\).

Next, we use breadth-first search to find the minimum number of jumps. We maintain a queue \(q\) to store the indices that can currently be reached, with only index \(0\) in \(q\) initially. Each time we pop an index \(i\) from \(q\), if \(i\) is the target index \(n - 1\), we return the current number of jumps. Otherwise, we add all indices in \(g[nums[i]]\) to \(q\) and remove them from \(g[nums[i]]\) to avoid repeated visits. At the same time, we also add the adjacent indices \(i + 1\) and \(i - 1\) to \(q\) if they are within bounds.

The time complexity is \(O(n \log M)\), and the space complexity is \(O(n \log M)\), where \(n\) is the length of the array, and \(M\) is the maximum value in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
mx = 10**6 + 1
factors = [[] for _ in range(mx)]
for i in range(2, mx):
    if not factors[i]:
        for j in range(i, mx, i):
            factors[j].append(i)


class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        g = defaultdict(list)
        for i, x in enumerate(nums):
            for p in factors[x]:
                g[p].append(i)
        ans = 0
        vis = [False] * n
        vis[0] = True
        q = [0]
        while 1:
            nq = []
            for i in q:
                if i == n - 1:
                    return ans
                idx = g[nums[i]]
                idx.append(i + 1)
                if i:
                    idx.append(i - 1)
                for j in idx:
                    if not vis[j]:
                        vis[j] = True
                        nq.append(j)
                idx.clear()
            q = nq
            ans += 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    private static final int mx = 1000001;
    private static final List<Integer>[] factors = new List[mx];

    static {
        for (int i = 0; i < mx; i++) {
            factors[i] = new ArrayList<>();
        }
        for (int i = 2; i < mx; i++) {
            if (factors[i].isEmpty()) {
                for (int j = i; j < mx; j += i) {
                    factors[j].add(i);
                }
            }
        }
    }

    public int minJumps(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int p : factors[x]) {
                g.computeIfAbsent(p, k -> new ArrayList<>()).add(i);
            }
        }
        int ans = 0;
        boolean[] vis = new boolean[n];
        vis[0] = true;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        while (true) {
            Deque<Integer> nq = new ArrayDeque<>();
            for (int i : q) {
                if (i == n - 1) {
                    return ans;
                }
                List<Integer> idx = g.getOrDefault(nums[i], new ArrayList<>());
                idx.add(i + 1);
                if (i > 0) {
                    idx.add(i - 1);
                }
                for (int j : idx) {
                    if (!vis[j]) {
                        vis[j] = true;
                        nq.offer(j);
                    }
                }
                idx.clear();
            }
            q = nq;
            ans++;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int mx = 1e6 + 1;
vector<int> factors[mx];

int init = [] {
    for (int i = 2; i < mx; ++i) {
        if (factors[i].empty()) {
            for (int j = i; j < mx; j += i) {
                factors[j].push_back(i);
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int minJumps(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> g;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int p : factors[x]) {
                g[p].push_back(i);
            }
        }
        int ans = 0;
        vector<bool> vis(n, false);
        vis[0] = true;
        queue<int> q;
        q.push(0);
        while (true) {
            queue<int> nq;
            while (!q.empty()) {
                int i = q.front();
                q.pop();
                if (i == n - 1) {
                    return ans;
                }
                vector<int> idx = g[nums[i]];
                idx.push_back(i + 1);
                if (i > 0) {
                    idx.push_back(i - 1);
                }
                for (int j : idx) {
                    if (!vis[j]) {
                        vis[j] = true;
                        nq.push(j);
                    }
                }
                g[nums[i]].clear();
            }
            q = nq;
            ans++;
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const mx = 1000001

var factors [mx][]int

func init() {
    for i := 2; i < mx; i++ {
        if len(factors[i]) == 0 {
            for j := i; j < mx; j += i {
                factors[j] = append(factors[j], i)
            }
        }
    }
}

func minJumps(nums []int) int {
    n := len(nums)
    g := make(map[int][]int)
    for i, x := range nums {
        for _, p := range factors[x] {
            g[p] = append(g[p], i)
        }
    }
    ans := 0
    vis := make([]bool, n)
    vis[0] = true
    q := []int{0}
    for {
        nq := []int{}
        for _, i := range q {
            if i == n-1 {
                return ans
            }
            idx := append([]int{}, g[nums[i]]...)
            idx = append(idx, i+1)
            if i > 0 {
                idx = append(idx, i-1)
            }
            for _, j := range idx {
                if !vis[j] {
                    vis[j] = true
                    nq = append(nq, j)
                }
            }
            g[nums[i]] = []int{}
        }
        q = nq
        ans++
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const mx = 1000001;
const factors: number[][] = Array(mx);

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

function minJumps(nums: number[]): number {
    const n = nums.length;
    const g = new Map<number, number[]>();
    for (let i = 0; i < n; i++) {
        const x = nums[i];
        for (const p of factors[x]) {
            if (!g.has(p)) {
                g.set(p, []);
            }
            g.get(p)!.push(i);
        }
    }
    let ans = 0;
    const vis = new Array(n).fill(false);
    vis[0] = true;
    let q: number[] = [0];
    while (true) {
        const nq: number[] = [];
        for (const i of q) {
            if (i === n - 1) {
                return ans;
            }
            const idx = [...(g.get(nums[i]) || [])];
            idx.push(i + 1);
            if (i > 0) {
                idx.push(i - 1);
            }
            for (const j of idx) {
                if (!vis[j]) {
                    vis[j] = true;
                    nq.push(j);
                }
            }
            if (g.has(nums[i])) {
                g.get(nums[i])!.length = 0;
            }
        }
        q = nq;
        ans++;
    }
}

Comments