Daily Problem for May 7th, 2026

Problem Statement

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

My Initial Solution

My first guess was DP, since there seems to be a very clear subproblem defined by the index 0 <= i <= n-1, where the value is the min number of jumps.

Then, I’d return the value of the 0th subproblem and start filling the table from n-1. So it was a bottom-up DP. I have pasted my code below:

class Solution:

    # bottom-up DP table filling approach
    # start with memo[n-1] = 0

    def minJumps(self, nums: List[int]) -> int:
        def isPrime(n: int) -> bool:
            if n == 0 or n == 1:
                return False
            
            for i in range(2, int(n ** 0.5) + 1):
                if n % i == 0:
                    return False
            
            return True

        n = len(nums)

        # fill all the possible jump successors and costs
        # succs = {i:set() for i in range(n)}
        prevs = {i:set() for i in range(n)}

        for i in range(n):
            if i+1 < n:
                prevs[i+1].add(i)
            if i-1 >= 0:
                prevs[i-1].add(i)

            if isPrime(nums[i]):
                # jumps still cost 1
                for j in range(n):
                    if j == i: # must be an index j != i
                        continue
                    elif nums[j] % nums[i] == 0:
                        prevs[j].add(i)
                

        # subproblems: for each index i, infinite jumps to start
        memo = [float('inf') for _ in range(n)]
        memo[n-1] = 0 # base case: already at n-1
        for i in reversed(range(n)):
            for s in prevs[i]:
                memo[s] = min(memo[i] + 1, memo[s])

            # print(i, succs[i], prevs[i], memo)           


        return memo[0]

This got me to pass 910/933 test cases. So I was hella confused, and given that I started at 11:30 PM, I turned to Google Gemini (because I’m an idiot who doesn’t follow my professor’s advice, and also because I was unsure if I wrote my isPrime function correctly. Idek how at first I wrote this monstrosity when just starting the problem:)

class Solution:

    # bottom-up DP table filling approach
    # start with memo[n-1] = 0

    def minJumps(self, nums: List[int]) -> int:
        def isPrime(n: int) -> bool:
            maxfac = int(n ** 0.5)
            memo = [False for _ in range(maxfac + 1)]
            # ignores divisible by 1, and ignores 0
            for i in range(2, maxfac + 1):
                if memo[i]:
                    continue
                elif n % i == 0:
                    memo[i] = True
            return any(memo)

        n = len(nums)

        # fill all the possible jump successors and costs
        succs = {i:[] for i in range(n)}
        for i in range(n):
            if i+1 < n:
                succs[i].append((i+1, 1))
            if i-1 >= 0:
                succs[i].append((i-1, 1))
            if isPrime(nums[i]):
                teleports = list(filter(lambda j: nums[j] % nums[i] == 0, range(n)))
                teleports = list(filter(lambda j: i != j, teleports)) # any index j != i
                teleports = list(map(lambda dst: (dst, 0), teleports))
                succs[i].extend(teleports)
                
        print(succs)

        prevs = {i:set() for i in range(n)}
        for i in range(n):
            scs = succs[i]
            for sc, cost in scs:
                prevs[sc].add((i, cost))
        print(prevs)
        return 0

I mean, WHAT AM I DOING why is my isPrime function absolutely stupid, and what am I doing with the prevs and succs?

To that end, I kinda noticed that the preds was just the graph transpose of the succs adjacency list, which was probably a sign that this was a graph algo and not DP… alas I am not intelligent.

The True Solution, a-la Gemini

I asked Gemini to verify my isPrime function and it suggested that I be a little smarter, but overall fine. I didn’t bother with a Sieve of Erastothenes but ig that would’ve been faster - but that wouldn’t have solved the nagging feeling that this was a graph problem, not a DP problem. So wth about 7 minutes left in the day, I just asked Gemini to figure out wtf was wrong with my code, and lo and behold, the entire algorithm was wrong.

Instead of doing DP, which table fills from n-1 to 0 without going back a second time, the intended approach was BFS.

from collections import deque, defaultdict

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

        # 1. Standard Prime Sieve (up to max value in nums)
        max_num = max(nums)
        is_prime_bit = [True] * (max_num + 1)
        is_prime_bit[0] = is_prime_bit[1] = False
        for p in range(2, int(max_num**0.5) + 1):
            if is_prime_bit[p]:
                for i in range(p * p, max_num + 1, p):
                    is_prime_bit[i] = False

        # 2. Map primes to indices of their multiples
        # We only care about primes that actually appear as a nums[i]
        primes_in_nums = {x for x in nums if x > 1 and is_prime_bit[x]}
        prime_to_indices = defaultdict(list)
        
        for i, val in enumerate(nums):
            # For each prime p in our set, if val is a multiple, record it
            # To stay efficient, we only check primes that are factors of val
            temp = val
            d = 2
            while d * d <= temp:
                if temp % d == 0:
                    if d in primes_in_nums:
                        prime_to_indices[d].append(i)
                    while temp % d == 0:
                        temp //= d
                d += 1
            if temp > 1 and temp in primes_in_nums:
                prime_to_indices[temp].append(i)

        # 3. BFS
        queue = deque([(0, 0)])  # (current_index, distance)
        visited = {0}
        visited_primes = set()

        while queue:
            curr, dist = queue.popleft()

            if curr == n - 1:
                return dist

            # Adjacent Step: i+1 and i-1
            for neighbor in [curr - 1, curr + 1]:
                if 0 <= neighbor < n and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))

            # Prime Teleportation
            p = nums[curr]
            if p in primes_in_nums and p not in visited_primes:
                visited_primes.add(p)
                for target_idx in prime_to_indices[p]:
                    if target_idx not in visited:
                        visited.add(target_idx)
                        queue.append((target_idx, dist + 1))

        return -1

Self-Reflection

Algo Design Technique

I mean it’s just a shortest path algo. Each jump is just an unweighted edge, edges must be (i, i+1), (i, i-1), or (i, j) with the prime-check. Then it’s just a BFS from vertex n-1 to 0, or vice versa. Get the length of that path and we’re done. Honestly could be an OK 210 question…

What I did well

I quickly figured out that computing the valid jumps on-the-fly was costly, and it was smart to precompute the successors (and eventually, just the predecessors) ahead of time using the isPrime function.

What I did badly

I got way too stuck in thinking it was DP because I saw an optimization problem with nice subproblems, and ignored my gut feeling that this problem was somehow a graph problem.

I also dillydallied for 15 minutes initially trying to do the problem in C++, only to remember that I am way more comfortable using Python. Welp.