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

Solutions

Solution 1

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++;
        }
    }
}

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++;
        }
    }
};

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

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++
	}
}

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++;
    }
}

3629 - Minimum Jumps to Reach End via Prime Teleportation

3629. Minimum Jumps to Reach End via Prime Teleportation

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3629. Minimum Jumps to Reach End via Prime Teleportation

Description

Solutions

Solution 1

All Problems

All Solutions