Minimum jumps to reach end via prime teleportation

Array Hash Table Math Breadth-First Search Number Theory

31.8% acceptance

Feb 25, 2026

130

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_jumps(nums: Vec<i32>) -> i32 {
    use std::collections::{BinaryHeap, HashMap, HashSet};
    use std::cmp::Reverse;
    let n = nums.len();
    if n == 1 { return 0; }

    // Find all prime factors for each element
    let max_val = *nums.iter().max().unwrap() as usize;
    // Smallest prime factor sieve
    let mut spf = (0..=max_val).collect::<Vec<usize>>();
    let mut i = 2;
    while i * i <= max_val {
      if spf[i] == i {
        let mut j = i * i;
        while j <= max_val {
          if spf[j] == j { spf[j] = i; }
          j += i;
        }
      }
      i += 1;
    }

    // Build prime -> list of indices
    let mut prime_to_indices: HashMap<usize, Vec<usize>> = HashMap::new();
    for (idx, &v) in nums.iter().enumerate() {
      let mut v = v as usize;
      let mut seen_primes = HashSet::new();
      while v > 1 {
        let p = spf[v];
        if seen_primes.insert(p) {
          prime_to_indices.entry(p).or_default().push(idx);
        }
        while v % p == 0 { v /= p; }
      }
    }

    let mut dist = vec![i32::MAX; n];
    dist[0] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0, 0usize)));
    let mut used_primes: HashSet<usize> = HashSet::new();

    while let Some(Reverse((d, u))) = heap.pop() {
      if d > dist[u] { continue; }
      if u == n - 1 { return d; }
      // Adjacent steps
      for nv in [u.wrapping_sub(1), u + 1] {
        if nv < n && dist[nv] > d + 1 {
          dist[nv] = d + 1;
          heap.push(Reverse((d + 1, nv)));
        }
      }
      // Prime teleportation from u via primes of nums[u]
      let mut v = nums[u] as usize;
      let mut seen = HashSet::new();
      while v > 1 {
        let p = spf[v];
        if seen.insert(p) {
          // Check if nums[u] itself is prime (p == nums[u])
          // Actually: teleportation is only if nums[u] is prime
          // But from the problem: "If nums[i] is a prime number p, you may jump to any j where nums[j] % p == 0"
          // nums[u] must BE a prime
          if nums[u] as usize == p && !used_primes.contains(&p) {
            used_primes.insert(p);
            if let Some(targets) = prime_to_indices.get(&p) {
              for &j in targets {
                if j != u && dist[j] > d + 1 {
                  dist[j] = d + 1;
                  heap.push(Reverse((d + 1, j)));
                }
              }
            }
          }
        }
        while v % p == 0 { v /= p; }
      }
    }
    dist[n - 1]
  }
}