3629. Minimum Jumps to Reach End via Prime Teleportation

/* 演算法 / Algorithm:
 * 1. 線性最小質因數篩 (SPF) 預先算好 spf[x]，使每個值能在 O(log x) 內分解。
 *    Build a smallest-prime-factor sieve so any value factors in O(log x).
 * 2. 對每個 nums[i] 取出相異質因數 p，把 i 放進 bucket[p]。
 *    For each value, push its index into bucket[p] for every distinct prime p.
 * 3. 從索引 0 做 BFS：鄰居是 i±1；若 nums[i] 是質數 p，再加上 bucket[p]
 *    內所有索引，然後清空該桶（同一個桶只展開一次，避免 O(n^2)）。
 *    BFS from index 0 with adjacency edges and prime-bucket edges; each
 *    bucket fires only once (we clear it after use) so total work is O(n).
 */
int minJumps(int* nums, int numsSize) {
    int n = numsSize;                                       // n 是陣列長度 / array length
    if (n == 1) return 0;                                   // 起點即終點 / already at goal

    int maxv = 1;                                           // 紀錄最大值 / track max value
    for (int i = 0; i < n; i++) {
        if (nums[i] > maxv) maxv = nums[i];                 // 比較並更新 / update if larger
    }

    /* ---- 最小質因數篩 / Smallest-prime-factor sieve ----
       calloc 配置記憶體並全填 0 / calloc allocates and zeroes the buffer */
    int* spf = (int*)calloc(maxv + 1, sizeof(int));
    for (int i = 2; i <= maxv; i++) {                       // 從 2 起檢查 / scan from 2
        if (spf[i] == 0) {                                  // 0 表示 i 是質數 / i is prime
            for (int j = i; j <= maxv; j += i) {            // 標記 i 的所有倍數 / mark multiples of i
                if (spf[j] == 0) spf[j] = i;                // 只在尚未填寫時寫入，保留最小者 / keep the smallest prime
            }
        }
    }

    /* ---- 第一輪：算每個質數桶要多少格 ----
       First pass: count how many entries each bucket will hold. */
    int* bcount = (int*)calloc(maxv + 1, sizeof(int));      // 桶大小 / bucket sizes
    for (int i = 0; i < n; i++) {
        int v = nums[i];                                    // v 是可破壞的拷貝 / mutable copy
        while (v > 1) {                                     // 拆掉所有質因數 / peel off all prime factors
            int p = spf[v];                                 // 取最小質因數 / smallest prime factor of v
            bcount[p]++;                                    // 此桶 +1 / bucket size += 1
            while (v % p == 0) v /= p;                      // 把 v 中所有 p 除掉，避免重複加 / strip all copies of p
        }
    }

    /* ---- 用前綴和算每個桶在扁平陣列中的起點 ----
       Prefix-sum the counts to get each bucket's start offset in a flat array. */
    int* boff = (int*)malloc((maxv + 2) * sizeof(int));     // boff[p] = 桶 p 起點 / start of bucket p
    boff[0] = 0;
    for (int i = 0; i <= maxv; i++) {
        boff[i + 1] = boff[i] + bcount[i];                  // 累加 / running sum
    }
    int total = boff[maxv + 1];                             // 所有桶總條目數 / total entries across all buckets

    int* bdata = (int*)malloc((total > 0 ? total : 1) * sizeof(int));  // 扁平資料區 / flat storage
    int* bfill = (int*)calloc(maxv + 1, sizeof(int));       // 各桶寫入指標 / per-bucket write cursor

    /* ---- 第二輪：把索引塞進桶 / Second pass: actually fill buckets. ---- */
    for (int i = 0; i < n; i++) {
        int v = nums[i];
        while (v > 1) {
            int p = spf[v];
            bdata[boff[p] + bfill[p]++] = i;                // 寫到桶尾並把指標往前推 / append and advance cursor
            while (v % p == 0) v /= p;
        }
    }

    /* ---- BFS 距離陣列與佇列 / BFS distance array and queue ---- */
    int* dist = (int*)malloc(n * sizeof(int));              // dist[i] = 從 0 到 i 的最短跳數 / shortest jumps to i
    for (int i = 0; i < n; i++) dist[i] = -1;               // -1 代表還沒拜訪 / unvisited sentinel

    int* queue = (int*)malloc(n * sizeof(int));             // 環狀不需要：節點最多入隊一次 / each node is pushed at most once
    int qh = 0, qt = 0;                                     // 頭尾指標 / head and tail cursors
    queue[qt++] = 0;                                        // 推入起點 / push start index
    dist[0] = 0;                                            // 起點距離為 0 / start has distance 0

    int ans = -1;                                           // 預設答案 / default answer
    while (qh < qt) {                                       // 佇列非空 / while queue is non-empty
        int i = queue[qh++];                                // 取出隊首 / pop the front
        if (i == n - 1) { ans = dist[i]; break; }           // 抵達終點即可離開 / early exit at goal
        int d = dist[i];                                    // 當前距離 / current distance

        /* 相鄰步 / Adjacent steps */
        if (i + 1 < n && dist[i + 1] == -1) {               // 右鄰未訪問 / right neighbor unvisited
            dist[i + 1] = d + 1;                            // 距離 +1 / one more jump
            queue[qt++] = i + 1;                            // 入隊 / enqueue
        }
        if (i - 1 >= 0 && dist[i - 1] == -1) {              // 左鄰未訪問 / left neighbor unvisited
            dist[i - 1] = d + 1;
            queue[qt++] = i - 1;
        }

        /* 質數傳送 / Prime teleportation (only when nums[i] itself is prime) */
        int v = nums[i];
        if (v >= 2 && spf[v] == v) {                        // spf[v]==v 即 v 是質數 / v is prime
            int sz = bcount[v];                             // 桶內剩多少個 / remaining bucket size
            int start = boff[v];                            // 桶起始位置 / bucket start offset
            for (int k = 0; k < sz; k++) {
                int j = bdata[start + k];                   // 桶內第 k 個索引 / k-th index in the bucket
                if (dist[j] == -1) {                        // 尚未拜訪才更新 / only first visit wins (BFS optimal)
                    dist[j] = d + 1;
                    queue[qt++] = j;
                }
            }
            bcount[v] = 0;                                  // 清空桶：之後同樣的 p 不再重展 / clear bucket so each prime fires once
        }
    }

    /* 釋放所有 malloc/calloc 配置的記憶體 / Free every heap allocation */
    free(spf); free(bcount); free(boff);
    free(bdata); free(bfill); free(dist); free(queue);
    return ans;
}

/* 演算法 / Algorithm:
 * 1. 用 SPF 篩預算最小質因數 / SPF sieve up to max(nums).
 * 2. 為每個出現的相異質因數 p 建桶 bucket[p] / build bucket[p] of indices divisible by p.
 * 3. BFS：相鄰邊 + 若 nums[i] 是質數 p 則展開 bucket[p] 後清空 / BFS with prime-bucket edges, clearing buckets after use.
 */
class Solution {
public:
    int minJumps(vector<int>& nums) {
        int n = (int)nums.size();                                 // 陣列長度 / array length
        if (n == 1) return 0;                                     // 已在終點 / already at goal

        // *max_element 回傳指向最大元素的迭代器，前面加 * 取值 / returns iterator; * dereferences it
        int maxv = *max_element(nums.begin(), nums.end());

        // vector<int>(size, init): 建立大小為 size、初值為 init 的動態陣列 / sized + initialized vector
        vector<int> spf(maxv + 1, 0);
        for (int i = 2; i <= maxv; ++i) {
            if (spf[i] == 0) {                                    // i 是質數 / i is prime
                for (int j = i; j <= maxv; j += i) {              // 走訪所有倍數 / walk multiples
                    if (spf[j] == 0) spf[j] = i;                  // 只在還沒寫過時寫，保留最小 / keep smallest factor
                }
            }
        }

        // unordered_map: 雜湊表，平均 O(1) 查找 / hash map with avg O(1) lookup
        // vector<int>: 每個質數對應的索引列表 / per-prime list of indices
        unordered_map<int, vector<int>> bucket;
        for (int i = 0; i < n; ++i) {
            int v = nums[i];
            while (v > 1) {                                       // 持續拆出質因數 / peel prime factors
                int p = spf[v];
                bucket[p].push_back(i);                           // 加進桶尾 / append index to bucket
                while (v % p == 0) v /= p;                        // 把所有 p 除掉，避免同一個 p 加兩次 / strip all copies of p
            }
        }

        vector<int> dist(n, -1);                                  // -1 表示未訪 / -1 = unvisited
        queue<int> q;                                             // STL FIFO 佇列 / FIFO queue
        q.push(0);
        dist[0] = 0;

        while (!q.empty()) {
            int i = q.front();                                    // 看隊首 / peek front
            q.pop();                                              // 真正彈出 / pop it (q.pop returns void)
            if (i == n - 1) return dist[i];                       // 到終點即返回 / early exit
            int d = dist[i];

            // 範圍 for + initializer_list 一次處理兩個鄰居 / range-for over a brace-list iterates {i-1, i+1}
            for (int ni : {i - 1, i + 1}) {
                if (ni >= 0 && ni < n && dist[ni] == -1) {        // 邊界內且未訪 / in-bounds and unvisited
                    dist[ni] = d + 1;
                    q.push(ni);
                }
            }

            int v = nums[i];
            if (v >= 2 && spf[v] == v) {                          // v 是質數 / v is prime
                auto it = bucket.find(v);                         // it 是迭代器 / iterator into the map
                if (it != bucket.end()) {                         // 桶存在 / bucket exists
                    for (int j : it->second) {                    // it->second 是 vector<int> / second = the index list
                        if (dist[j] == -1) {
                            dist[j] = d + 1;
                            q.push(j);
                        }
                    }
                    it->second.clear();                           // 清空桶以避免重展 / clear so each prime fires once
                }
            }
        }
        return dist[n - 1];                                       // 理論上必能到達 / always reachable in practice
    }
};