LeetCode 818: Race Car

Problem Restatement

We have a race car on an infinite number line.

The car starts at:

position = 0
speed = 1

There are two possible instructions.

The "R" instruction changes only the direction and resets speed magnitude to 1. It does not change the position.

Given an integer target, return the length of the shortest instruction sequence that makes the car reach exactly target. The car is allowed to move into negative positions.

Input and Output

Examples

Example 1:

target = 3

Use:

"AA"

Simulation:

The answer is:

2

Example 2:

target = 6

One shortest sequence is:

"AAARA"

Simulation:

The answer is:

5

First Thought: BFS Over States

A direct way is BFS over states:

(position, speed)

Each edge is one instruction, either "A" or "R".

Since every instruction has cost 1, BFS can find the shortest sequence.

This works, but the state space is large. We need bounds to avoid exploring too far. A dynamic programming solution is more compact because the target is one-dimensional.

Key Insight

After driving forward with k accelerations from position 0, the car reaches:

1 + 2 + 4 + ... + 2^(k - 1) = 2^k - 1

So positions of the form:

2^k - 1

are reachable using exactly k instructions.

For a target t, let k be the smallest integer such that:

2^k - 1 >= t

There are two main strategies.

First, if 2^k - 1 == t, just accelerate k times.

Second, if we overshoot to 2^k - 1, reverse, then solve the remaining distance:

(2^k - 1) - t

Third, we may stop before the target. Drive forward k - 1 times to reach:

2^(k - 1) - 1

Then reverse, drive backward for j accelerations, reverse again, and solve the remaining distance.

Algorithm

Let:

dp[t] = minimum instructions needed to reach position t

Use memoized recursion.

For a target t:

1. Find k = t.bit_length().
2. Let:

forward = (1 << k) - 1

3. If forward == t, return k.

4. Try overshooting:

k + 1 + dp(forward - t)

This means:

k accelerations + 1 reverse + solve remaining distance

5. Try stopping short.

Let:

before = (1 << (k - 1)) - 1

Then for each j from 0 to k - 2, drive backward j accelerations after reversing.

The backward distance is:

back = (1 << j) - 1

The remaining distance is:

t - (before - back)

The instruction count is:

(k - 1) + 1 + j + 1 + dp(remaining)

That is:

forward accelerations + reverse + backward accelerations + reverse + solve remaining

Return the minimum among these choices.

Correctness

The car’s forward-only position after k accelerations is exactly 2^k - 1, because each acceleration moves by the current speed and then doubles the speed.

For a target t, choose the first forward-only position that reaches or passes t.

If it equals t, no shorter sequence can use fewer than k accelerations to reach that far from the start, so returning k is correct.

If it passes t, one valid optimal form is to overshoot, reverse, and solve the remaining distance back toward the target. This gives the overshoot candidate.

The other possible optimal form is to reverse before reaching or passing the target. After k - 1 accelerations, the car is at the largest forward-only position still below t. If it reverses there, it may move backward for j accelerations, reverse again, and then solve a smaller forward subproblem. The algorithm checks every possible j, so it considers every such early-reverse strategy.

The recurrence therefore covers all optimal first phases: either reach exactly, overshoot once, or stop short and reverse back by some amount before continuing. Since each remaining part is solved optimally by dp, the computed minimum is the true shortest instruction length.

Complexity

Let T = target.

Implementation

from functools import cache

class Solution:
    def racecar(self, target: int) -> int:
        @cache
        def dp(t: int) -> int:
            k = t.bit_length()
            forward = (1 << k) - 1

            if forward == t:
                return k

            best = k + 1 + dp(forward - t)

            before = (1 << (k - 1)) - 1

            for j in range(k - 1):
                back = (1 << j) - 1
                remaining = t - (before - back)

                best = min(
                    best,
                    (k - 1) + 1 + j + 1 + dp(remaining),
                )

            return best

        return dp(target)

Code Explanation

The recursive function solves one distance:

def dp(t: int) -> int:

We compute the number of accelerations needed to reach or pass t:

k = t.bit_length()
forward = (1 << k) - 1

If forward == t, then k accelerations land exactly on the target:

if forward == t:
    return k

The overshoot option drives to forward, reverses, and solves the extra distance:

best = k + 1 + dp(forward - t)

Then we try stopping short:

before = (1 << (k - 1)) - 1

For each possible backward run:

for j in range(k - 1):

we compute how far backward it goes:

back = (1 << j) - 1

The position after going forward, reversing, going backward, and reversing again is:

before - back

So the remaining distance is:

remaining = t - (before - back)

The command count for this strategy is:

(k - 1) + 1 + j + 1 + dp(remaining)

Finally, the smallest strategy is returned.

Testing

def run_tests():
    s = Solution()

    assert s.racecar(1) == 1
    assert s.racecar(2) == 4
    assert s.racecar(3) == 2
    assert s.racecar(4) == 5
    assert s.racecar(5) == 7
    assert s.racecar(6) == 5

    print("all tests passed")

run_tests()