3629. Minimum Jumps to Reach End via Prime Teleportation

Time: O(N log log N)

Space: O(N + max_val)

Intuition

Indices whose values share a prime factor can teleport to each other in one jump, so the problem is shortest-path on an implicit graph. BFS guarantees the minimum number of jumps. The key insight is to group indices by prime factor and expand the whole group at once — then clear the group to prevent re-processing, keeping BFS linear in the number of edges rather than quadratic.

Algorithm

1Precompute a sieve: for every integer 2 to 1e6, record all its prime factors.
2Walk nums[] and build a map: prime → list of indices that have that prime.
3BFS from index 0 with a visited array.
4For each dequeued index i: if i == n-1 return current depth (ans).
5Collect neighbors: all indices sharing a prime with nums[i], plus i-1 and i+1.
6After expanding a prime group, clear it from the map so it is never traversed again.
7Enqueue unvisited neighbors; increment ans after each full BFS layer.

Example Walkthrough

Input: nums = [6, 10, 15, 35, 21]

1.Primes of each: 6→{2,3}, 10→{2,5}, 15→{3,5}, 35→{5,7}, 21→{3,7}.
2.BFS layer 0: visit index 0 (value 6).
3.Layer 1: expand prime 2 → indices {0,1}; prime 3 → indices {0,2,4}; also i+1=1. New: 1,2,4.
4.Layer 2: from index 1, prime 5 → indices {1,2,3}; new: 3. From index 2 or 4, i+1=3,5 would reach end.
5.index 4 → i+1=5 (n-1=4 in a 5-element array) … return ans = 2.

Output: 2

Common Pitfalls

•Not clearing the prime-group after use causes O(N²) re-expansion and TLE.
•Static initialization of the sieve (in the static constructor) means it is built only once per program run — essential for passing multiple test cases efficiently.
•Remember to also add i+1 and i-1 to the neighbor list, not just the prime-teleport neighbors.

3629.cs

// Approach: Precompute all prime factors for every number up to 1e6 with a linear sieve.
// Build an adjacency map: prime → list of indices whose value has that prime factor.
// BFS from index 0; at each step expand to i-1, i+1, and all indices sharing a prime factor with nums[i].
// Clear each prime's index list after expansion to avoid re-visiting the same group.
// Time: O(N log log N) Space: O(N + max_val)

public class Solution
{
    private const int mx = 1000001;
    private static readonly List<int>[] factors = new List<int>[mx];

    static Solution()
    {
        for (int i = 0; i < mx; i++)
            factors[i] = new List<int>();

        for (int i = 2; i < mx; i++)
        {
            if (factors[i].Count == 0)
            {
                for (int j = i; j < mx; j += i)
                    factors[j].Add(i);
            }
        }
    }

    public int MinJumps(int[] nums)
    {
        int n = nums.Length;
        var g = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++)
        {
            int x = nums[i];
            foreach (int p in factors[x])
            {
                if (!g.ContainsKey(p))
                    g[p] = new List<int>();
                g[p].Add(i);
            }
        }

        int ans = 0;
        bool[] vis = new bool[n];
        vis[0] = true;
        var q = new Queue<int>();
        q.Enqueue(0);
        while (true)
        {
            var nq = new Queue<int>();
            while (q.Count > 0)
            {
                int i = q.Dequeue();
                if (i == n - 1)
                    return ans;

                List<int> idx;
                if (!g.TryGetValue(nums[i], out idx))
                    idx = new List<int>();

                idx.Add(i + 1);
                if (i > 0)
                    idx.Add(i - 1);

                foreach (int j in idx)
                {
                    if (j >= 0 && j < n && !vis[j])
                    {
                        vis[j] = true;
                        nq.Enqueue(j);
                    }
                }
                idx.Clear();
            }
            q = nq;
            ans++;
        }
    }
}

Was this solution helpful?