0797MediumArrayHash TableMathBreadth-First SearchNumber Theory

Relay Hops Along the Valve Line

Tracked in this browser only

Trains the technique from

LeetCode 3629Minimum Jumps to Reach End via Prime Teleportation

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A survey robot works a straight line of valves numbered 0 to n - 1. Valve i is stamped with a pressure rating rating[i]. The robot starts at valve 0 and has to reach valve n - 1.

From valve i the robot can make either kind of move, and each move counts as one:

step: go to valve i - 1 or valve i + 1, when that valve exists;
relay: only if rating[i] is a prime number, go to any valve j whose rating is a multiple of rating[i], that is rating[j] % rating[i] == 0. Valve j may lie anywhere on the line, before or after valve i.

The number 1 is not prime, so a valve rated 1 can never relay.

Return the least number of moves the robot needs to reach valve n - 1. When the line holds a single valve the robot is already there, so the answer is 0.

Examples

Example 1

Input: rating = [2, 7, 9, 4, 8]
Output: 1

Valve 0 is rated 2, which is prime, and valve 4 is rated 8, a multiple of 2, so one relay takes the robot straight to the last valve.

Example 2

Input: rating = [1, 1, 1, 1]
Output: 3

Every valve is rated 1, which is not prime, so no relay is available and the robot steps from valve 0 to valve 3 one valve at a time.

Example 3

Input: rating = [6, 4, 7, 10, 9, 21, 2]
Output: 4

One route in four moves: step to valve 1, step to valve 2, relay from the prime rating 7 to valve 5 whose rating 21 is a multiple of 7, then step to valve 6.

Constraints

1 <= rating.length <= 10^5
1 <= rating[i] <= 10^6

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_moves(rating: list[int]) -> int:

Java

public int fewestMoves(int[] rating)

The intended approach

Time O(M log log M + n log M + n) for n valves and largest rating M: the sieve, then a bounded number of prime factors per rating, then a sweep in which each valve and each group entry is used once.Space O(M + n log M) for the sieve, the prime groups and the distance array.

Sieve the smallest prime factor up to the largest rating, then group the valves: for every prime p, the list of valves whose rating p divides, found by factoring each rating through the sieve. Because every move costs one, a breadth-first sweep from valve 0 gives the answer; a valve with a prime rating hands the whole group for that prime to the queue, and the group is then dropped, so no group is ever expanded twice.

Pythonentry point: fewest_moves

def fewest_moves(rating):
    n = len(rating)
    if n == 1:
        return 0
    top = max(rating)
    # smallest prime factor sieve, so factoring a rating is a few divisions
    spf = list(range(top + 1))
    i = 2
    while i * i <= top:
        if spf[i] == i:
            for m in range(i * i, top + 1, i):
                if spf[m] == m:
                    spf[m] = i
        i += 1
    holders = {}
    for idx, v in enumerate(rating):
        x = v
        while x > 1:
            p = spf[x]
            holders.setdefault(p, []).append(idx)
            while x % p == 0:
                x //= p
    dist = [-1] * n
    dist[0] = 0
    queue = [0]
    at = 0
    while at < len(queue):
        here = queue[at]
        at += 1
        d = dist[here]
        reach = [here - 1, here + 1]
        v = rating[here]
        if v > 1 and spf[v] == v:
            # a prime rating relays to every multiple; the group is spent once
            reach.extend(holders.pop(v, ()))
        for nxt in reach:
            if 0 <= nxt < n and dist[nxt] == -1:
                if nxt == n - 1:
                    return d + 1
                dist[nxt] = d + 1
                queue.append(nxt)
    return dist[n - 1]

The obvious version

Breadth-first search with the moves worked out from scratch: test the current rating for primality by trial division and, when it is prime, scan the whole line for valves whose rating it divides. No sieve and no grouping. O(n^2 sqrt(M)).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_moves(rating):
    n = len(rating)

    def is_prime(x):
        if x < 2:
            return False
        d = 2
        while d * d <= x:
            if x % d == 0:
                return False
            d += 1
        return True

    dist = [-1] * n
    dist[0] = 0
    queue = [0]
    at = 0
    while at < len(queue):
        here = queue[at]
        at += 1
        moves = []
        if here > 0:
            moves.append(here - 1)
        if here + 1 < n:
            moves.append(here + 1)
        if is_prime(rating[here]):
            for j in range(n):
                if rating[j] % rating[here] == 0:
                    moves.append(j)
        for j in moves:
            if dist[j] == -1:
                dist[j] = dist[here] + 1
                queue.append(j)
    return dist[n - 1]

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in