3629. Minimum Jumps to Reach End via Prime Teleportation

/**
 * Problem: LeetCode 3629 - Minimum Jumps to Reach End via Prime Teleportation
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

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

        int maxVal = 0;
        for (int x : nums) {
            if (x > maxVal) maxVal = x;
        }

        // Precompute Smallest Prime Factor (SPF)
        int[] spf = new int[maxVal + 1];
        for (int i = 0; i <= maxVal; i++) spf[i] = i;
        for (int i = 2; i * i <= maxVal; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j <= maxVal; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }

        // Map each prime factor to the list of indices whose value is divisible by it
        Map<Integer, List<Integer>> primeToIndices = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (x > 1) {
                int p = spf[x];
                primeToIndices.computeIfAbsent(p, k -> new ArrayList<>()).add(i);
                while (x % p == 0) x /= p;
            }
        }

        // BFS for shortest path (minimum jumps)
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[0] = 0;

        int[] queue = new int[n];
        int head = 0, tail = 0;
        queue[tail++] = 0;

        while (head < tail) {
            int u = queue[head++];
            int d = dist[u];

            if (u == n - 1) return d;

            // 1. Adjacent steps: u - 1 and u + 1
            if (u - 1 >= 0 && dist[u - 1] == -1) {
                dist[u - 1] = d + 1;
                if (u - 1 == n - 1) return d + 1;
                queue[tail++] = u - 1;
            }
            if (u + 1 < n && dist[u + 1] == -1) {
                dist[u + 1] = d + 1;
                if (u + 1 == n - 1) return d + 1;
                queue[tail++] = u + 1;
            }

            // 2. Prime Teleportation: if nums[u] is prime
            int val = nums[u];
            if (val >= 2 && spf[val] == val) {
                List<Integer> list = primeToIndices.remove(val);
                if (list != null) {
                    for (int v : list) {
                        if (dist[v] == -1) {
                            dist[v] = d + 1;
                            if (v == n - 1) return d + 1;
                            queue[tail++] = v;
                        }
                    }
                }
            }
        }

        return dist[n - 1];
    }
}

"""
Problem: LeetCode 3629 - Minimum Jumps to Reach End via Prime Teleportation
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List
from collections import deque, defaultdict

class Solution:
    def minJumps(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0

        max_val = max(nums)

        # Smallest Prime Factor (SPF) sieve
        spf = list(range(max_val + 1))
        for i in range(2, int(max_val**0.5) + 1):
            if spf[i] == i:
                for j in range(i * i, max_val + 1, i):
                    if spf[j] == j:
                        spf[j] = i

        # Group indices by prime factors
        prime_to_indices = defaultdict(list)
        for i, val in enumerate(nums):
            x = val
            while x > 1:
                p = spf[x]
                prime_to_indices[p].append(i)
                while x % p == 0:
                    x //= p

        # BFS for shortest path
        dist = [-1] * n
        dist[0] = 0
        queue = deque([0])

        while queue:
            u = queue.popleft()
            d = dist[u]

            if u == n - 1:
                return d

            # 1. Adjacent steps: u - 1 and u + 1
            if u - 1 >= 0 and dist[u - 1] == -1:
                dist[u - 1] = d + 1
                if u - 1 == n - 1:
                    return d + 1
                queue.append(u - 1)

            if u + 1 < n and dist[u + 1] == -1:
                dist[u + 1] = d + 1
                if u + 1 == n - 1:
                    return d + 1
                queue.append(u + 1)

            # 2. Prime Teleportation
            val = nums[u]
            if val >= 2 and spf[val] == val and val in prime_to_indices:
                for v in prime_to_indices[val]:
                    if dist[v] == -1:
                        dist[v] = d + 1
                        if v == n - 1:
                            return d + 1
                        queue.append(v)
                del prime_to_indices[val]

        return dist[n - 1]

/**
 * Problem: LeetCode 3629 - Minimum Jumps to Reach End via Prime Teleportation
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    int minJumps(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return 0;

        int maxVal = 0;
        for (int x : nums) {
            maxVal = max(maxVal, x);
        }

        // Smallest Prime Factor (SPF)
        vector<int> spf(maxVal + 1);
        for (int i = 0; i <= maxVal; ++i) spf[i] = i;
        for (int i = 2; i * 1LL * i <= maxVal; ++i) {
            if (spf[i] == i) {
                for (int j = i * i; j <= maxVal; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }

        // Map each prime to indices where nums[j] is divisible by that prime
        unordered_map<int, vector<int>> primeToIndices;
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            while (x > 1) {
                int p = spf[x];
                primeToIndices[p].push_back(i);
                while (x % p == 0) x /= p;
            }
        }

        // BFS for shortest path (minimum jumps)
        vector<int> dist(n, -1);
        dist[0] = 0;
        queue<int> q;
        q.push(0);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            int d = dist[u];

            if (u == n - 1) return d;

            // 1. Adjacent steps
            if (u - 1 >= 0 && dist[u - 1] == -1) {
                dist[u - 1] = d + 1;
                if (u - 1 == n - 1) return d + 1;
                q.push(u - 1);
            }
            if (u + 1 < n && dist[u + 1] == -1) {
                dist[u + 1] = d + 1;
                if (u + 1 == n - 1) return d + 1;
                q.push(u + 1);
            }

            // 2. Prime Teleportation
            int val = nums[u];
            if (val >= 2 && spf[val] == val) {
                auto it = primeToIndices.find(val);
                if (it != primeToIndices.end()) {
                    for (int v : it->second) {
                        if (dist[v] == -1) {
                            dist[v] = d + 1;
                            if (v == n - 1) return d + 1;
                            q.push(v);
                        }
                    }
                    primeToIndices.erase(it);
                }
            }
        }

        return dist[n - 1];
    }
};

/**
 * Problem: LeetCode 3629 - Minimum Jumps to Reach End via Prime Teleportation
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
var minJumps = function(nums) {
    const n = nums.length;
    if (n <= 1) return 0;

    let maxVal = 0;
    for (let i = 0; i < n; i++) {
        if (nums[i] > maxVal) maxVal = nums[i];
    }

    // Smallest Prime Factor (SPF) Sieve
    const spf = new Int32Array(maxVal + 1);
    for (let i = 0; i <= maxVal; i++) spf[i] = i;
    for (let i = 2; i * i <= maxVal; i++) {
        if (spf[i] === i) {
            for (let j = i * i; j <= maxVal; j += i) {
                if (spf[j] === j) spf[j] = i;
            }
        }
    }

    // Map each prime factor to the list of indices divisible by it
    const primeToIndices = new Map();
    for (let i = 0; i < n; i++) {
        let x = nums[i];
        while (x > 1) {
            const p = spf[x];
            let list = primeToIndices.get(p);
            if (!list) {
                list = [];
                primeToIndices.set(p, list);
            }
            list.push(i);
            while (x % p === 0) x = Math.floor(x / p);
        }
    }

    // BFS with queue
    const dist = new Int32Array(n).fill(-1);
    dist[0] = 0;
    const queue = new Int32Array(n);
    let head = 0, tail = 0;
    queue[tail++] = 0;

    while (head < tail) {
        const u = queue[head++];
        const d = dist[u];

        if (u === n - 1) return d;

        // 1. Adjacent steps: u - 1 and u + 1
        if (u - 1 >= 0 && dist[u - 1] === -1) {
            dist[u - 1] = d + 1;
            if (u - 1 === n - 1) return d + 1;
            queue[tail++] = u - 1;
        }
        if (u + 1 < n && dist[u + 1] === -1) {
            dist[u + 1] = d + 1;
            if (u + 1 === n - 1) return d + 1;
            queue[tail++] = u + 1;
        }

        // 2. Prime Teleportation: if nums[u] is prime
        const val = nums[u];
        if (val >= 2 && spf[val] === val) {
            const list = primeToIndices.get(val);
            if (list) {
                for (let i = 0; i < list.length; i++) {
                    const v = list[i];
                    if (dist[v] === -1) {
                        dist[v] = d + 1;
                        if (v === n - 1) return d + 1;
                        queue[tail++] = v;
                    }
                }
                primeToIndices.delete(val);
            }
        }
    }

    return dist[n - 1];
};