Loading page…
Practice problem · easy
A monitoring system sends a health signal along a line of relay stations numbered 0 to n - 1. The signal starts at station 0. A station can forward the signal to any station ahead of it, up to a fixed distance. Each forward adds delay.
Your team lead asks: "What is the fewest number of forwards needed to get the signal to the last station?"
Write fewest_forwards_to_the_end(hops).
hops[i] is the farthest ahead that station i can forward the signal. From station i the signal can go to any station from i + 1 to i + hops[i]. A value of 0 means the station cannot forward it.0 to station n - 1.-1 if the last station cannot be reached.Input: hops = [3, 1, 4, 1, 1, 2, 1]
Output: 2Think in rounds. Round 1 covers every station you can reach with one forward. Round 2 covers every station you can reach by forwarding from a round 1 station. Keep farthest, the farthest reach seen so far, and round_end, the last station of the current round.
| Station | farthest after | round_end | Forwards | What happens |
|---|---|---|---|---|
| 0 | 3 | 0 → 3 | 1 | Round 0 (no forwards) ends at station 0: count a forward, and round 1 covers up to 3 |
| 1 | 3 | 3 | 1 | 1 + 1 = 2, no gain |
| 2 | 6 | 3 | 1 | 2 + 4 = 6: station 2 reaches the last station |
| 3 | 6 | 3 → 6 | 2 | Round 1 ends at station 3: count a forward, and round 2 reaches the end |
Two forwards reach station 6, so the answer is 2: forward from station 0 to station 2, then to station 6.
Input: hops = [1, 1, 1, 1]
Output: 3Each station only reaches the next one, so the signal needs 3 forwards.
Input: hops = [2, 0, 0, 5]
Output: -1Station 0 reaches stations 1 and 2, but both have hops = 0. Nothing reaches station 3.
1 ≤ len(hops) ≤ 100,0000 ≤ hops[i] ≤ 100,000There can be 100,000 stations. The number of different ways to choose forwards can double at almost every station, so trying them all never finishes. A single pass that keeps two numbers costs 100,000 steps.
fewest_forwards_to_the_end · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.