Show problems as
Classic problem #3629MediumArrayHash TableMathBreadth-First SearchNumber Theory

Minimum Jumps to Reach End via Prime Teleportation

Real-world version: Relay Hops Along the Valve Line
Tracked in this browser only
Read Minimum Jumps to Reach End via Prime Teleportation on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_moves(rating: list[int]) -> int:
Java
public int fewestMoves(int[] rating)

More on the same topics