Classic problem #818HardDynamic ProgrammingHeuristic SearchA* Search
Race Car
Real-world version: Driving the Trolley to the MarkTracked in this browser only
Read Race Car on LeetCode(opens in a new tab)
The statement here is our own: the same inputs, outputs and technique.
A trolley stands at position 0 on a rail, facing forwards with a speed of 1.
Two controls are available:
- Push moves the trolley forward by its speed, then doubles that speed. Facing backwards the speed is negative, so the trolley moves backwards and the speed doubles in size.
- Turn sets the speed to
1when it was negative and to-1when it was positive. The trolley does not move.
Return the fewest presses needed to bring the trolley to position target.
Examples
Example 1
- Input
- target = 1
- Output
- 1
One push carries the trolley one place and it has arrived.
Example 2
- Input
- target = 7
- Output
- 3
Three pushes carry the trolley 1, then 2, then 4 places, which is exactly seven.
Example 3
- Input
- target = 4
- Output
- 5
Push twice to reach 3, then turn twice to bring the speed back to one without moving, and push once more to land on 4. A third push would have overshot to 7.
Constraints
- 1 <= target <= 10^4
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 racecar(target: int) -> int:Java
public int racecar(int target)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's