LeetCode Problem 818

Difficulty: 🔴 Hard
Topics: Dynamic Programming

Solution

LeetCode 818 - Race Car

Problem Understanding

This problem asks us to control a car moving on an infinite one dimensional number line. The car starts at position 0 with speed +1. We are allowed to issue two kinds of instructions:

• "A" for accelerate
• "R" for reverse

The "A" instruction moves the car forward according to its current speed, then doubles the speed. If the current speed is negative, the car moves backward and the magnitude of the speed doubles.

The "R" instruction does not move the car at all. Instead, it resets the speed direction:

• Positive speed becomes -1
• Negative speed becomes +1

The goal is to reach exactly the target position using the fewest instructions possible.

For example, if the target is 3, the sequence "AA" works:

• Start at (position=0, speed=1)
• First "A" → (1, 2)
• Second "A" → (3, 4)

The answer is therefore 2.

The constraints are important:

• 1 <= target <= 10^4

A target up to ten thousand is large enough that naive brute force exploration becomes impractical. We need a solution that avoids exploring every possible instruction sequence blindly.

An important observation is that repeated accelerations create positions of the form:

$$1, 3, 7, 15, 31, ...$$

These are:

$$2^k - 1$$

after k consecutive accelerations.

Several edge cases make this problem tricky:

• The target may already lie exactly on a position reachable with only accelerations.
• The optimal path may overshoot the target and come back.
• The optimal path may stop before the target, reverse, backtrack slightly, then continue forward again.
• The search space includes negative positions and alternating directions, which can explode combinatorially in naive solutions.

Because of these behaviors, simple greedy strategies do not work reliably.

Approaches

Brute Force Approach

The most straightforward idea is to model the problem as a graph search problem.

Each state consists of:

• Current position
• Current speed

From each state, we can generate two next states:

• Apply "A"
• Apply "R"

We could run Breadth First Search because every instruction costs exactly one step. BFS guarantees the first time we reach the target is the shortest sequence.

This approach is correct because BFS explores states in increasing order of instruction count.

However, the state space grows extremely quickly. Positions and speeds can become very large due to repeated doubling. Even with pruning, the number of reachable states becomes enormous.

For targets near 10^4, brute force BFS becomes inefficient.

Optimal Dynamic Programming Approach

The key insight is that acceleration creates very structured movement patterns.

After k accelerations:

$$position = 2^k - 1$$

This means we can think in terms of powers of two.

For any target:

• Either we reach it exactly using only accelerations
• Or we overshoot it and reverse
• Or we stop before it, reverse briefly, then continue

This naturally leads to dynamic programming.

Define:

$$dp[t]$$

as the minimum instructions needed to reach target t.

For each target, we compute the smallest k such that:

$$2^k - 1 \ge t$$

Then we consider two possibilities:

1. Overshoot the target and reverse back
2. Stop before the target, reverse for some distance, then move forward again

Because every subproblem involves smaller targets, memoization or bottom up DP works efficiently.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force BFS	Exponential	Exponential	Explores huge state space of positions and speeds
Optimal Dynamic Programming	O(target log target)	O(target)	Uses structure of acceleration distances

Algorithm Walkthrough

Step 1: Define the DP State

Let dp[t] represent the minimum number of instructions required to reach position t.

We want to compute:

$$dp[target]$$

Step 2: Find the Smallest Overshooting Power

For a given target t, determine the minimum number of accelerations k such that:

$$2^k - 1 \ge t$$

This corresponds to accelerating k times continuously.

The resulting position is:

$$full = 2^k - 1$$

Step 3: Handle Exact Match

If:

$$full = t$$

then we can reach the target directly with k accelerations.

So:

$$dp[t] = k$$

Step 4: Consider Overshooting

If full > t, we may:

1. Accelerate k times
2. Reverse once
3. Solve the remaining distance recursively

The remaining distance becomes:

$$full - t$$

The instruction count is:

$$k + 1 + dp[full - t]$$

where:

• k instructions for acceleration
• 1 instruction for reverse

Step 5: Consider Stopping Before the Target

Instead of overshooting, we can stop at:

$$2^{k-1} - 1$$

Then:

1. Reverse
2. Move backward with m accelerations
3. Reverse again
4. Continue toward the target

Backward movement after m accelerations covers:

$$2^m - 1$$

The remaining forward distance becomes:

$$t - (2^{k-1} - 1) + (2^m - 1)$$

The total instructions are:

$$(k - 1) + 1 + m + 1 + dp[\text{remaining}]$$

We try all valid m values and take the minimum.

Step 6: Memoize Results

Since many subproblems repeat, memoization avoids recomputation.

This reduces the complexity dramatically.

Why it works

The algorithm works because every optimal sequence must eventually fall into one of two categories:

• Overshoot the target and reverse
• Stop before the target, partially backtrack, then continue

The DP recurrence exhaustively considers both possibilities. Since each recursive call solves a strictly smaller target, memoization guarantees efficient computation and optimality.

Python Solution

class Solution:
    def racecar(self, target: int) -> int:
        memo = {0: 0}

        def dp(t: int) -> int:
            if t in memo:
                return memo[t]

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

            # Exact match
            if full_distance == t:
                memo[t] = k
                return k

            # Case 1: Overshoot and reverse
            result = k + 1 + dp(full_distance - t)

            # Case 2: Stop before target, reverse, backtrack, reverse again
            partial_distance = (1 << (k - 1)) - 1

            for m in range(k - 1):
                backward_distance = (1 << m) - 1

                remaining = (
                    t
                    - partial_distance
                    + backward_distance
                )

                instructions = (
                    (k - 1)     # forward accelerations
                    + 1         # reverse
                    + m         # backward accelerations
                    + 1         # reverse again
                    + dp(remaining)
                )

                result = min(result, instructions)

            memo[t] = result
            return result

        return dp(target)

The implementation uses top down memoized dynamic programming.

The memo dictionary stores previously computed answers. This prevents exponential recomputation of overlapping subproblems.

The expression:

t.bit_length()

computes the smallest k such that:

$$2^k > t$$

which helps determine the first acceleration sequence that reaches or exceeds the target.

The variable full_distance represents the position reached after k accelerations:

(1 << k) - 1

If this exactly equals the target, then the answer is simply k.

Otherwise, the code evaluates both recurrence options:

• Overshoot and reverse
• Stop early, reverse, partially backtrack, then continue

The loop over m explores every possible backward acceleration count before turning forward again.

Finally, the minimum result is memoized and returned.

Go Solution

package main

func racecar(target int) int {
	memo := map[int]int{
		0: 0,
	}

	var dp func(int) int

	dp = func(t int) int {
		if val, exists := memo[t]; exists {
			return val
		}

		k := 0
		for (1<<k)-1 < t {
			k++
		}

		fullDistance := (1 << k) - 1

		// Exact match
		if fullDistance == t {
			memo[t] = k
			return k
		}

		// Case 1: Overshoot and reverse
		result := k + 1 + dp(fullDistance-t)

		partialDistance := (1 << (k - 1)) - 1

		// Case 2: Stop before target
		for m := 0; m < k-1; m++ {
			backwardDistance := (1 << m) - 1

			remaining := t - partialDistance + backwardDistance

			instructions :=
				(k - 1) +
					1 +
					m +
					1 +
					dp(remaining)

			if instructions < result {
				result = instructions
			}
		}

		memo[t] = result
		return result
	}

	return dp(target)
}

The Go implementation follows the same recurrence structure as the Python version.

Since Go does not provide Python's bit_length() method, we compute k manually using a loop.

The memoization table uses a map[int]int. Recursive closures in Go require declaring the function variable before assigning the implementation.

Integer overflow is not a concern because the target constraint is only 10^4, and all intermediate values remain safely within Go's integer range.

Worked Examples

Example 1

Input:

target = 3

We compute:

k	Position After k Accelerations
1	1
2	3

Since:

$$2^2 - 1 = 3$$

we can reach the target exactly with "AA".

Step	Instruction	Position	Speed
Start	-	0	1
1	A	1	2
2	A	3	4

Answer:

2

Example 2

Input:

target = 6

Find smallest k:

k	Position
1	1
2	3
3	7

Now:

$$7 > 6$$

So we overshoot.

Sequence:

AAA

reaches position 7.

Then reverse:

AAAR

Now speed becomes -1.

One backward acceleration:

AAARA

moves from 7 to 6.

Step	Instruction	Position	Speed
Start	-	0	1
1	A	1	2
2	A	3	4
3	A	7	8
4	R	7	-1
5	A	6	-2

Answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(target log target)	Each target explores at most logarithmically many transitions
Space	O(target)	Memoization table stores one result per target

For each target t, we compute transitions involving at most O(log t) possibilities because the number of acceleration levels is logarithmic.

Since each target is memoized exactly once, the overall complexity becomes:

$$O(target \log target)$$

The memoization dictionary stores results for targets from 0 to target, giving linear space usage.

Test Cases

sol = Solution()

assert sol.racecar(1) == 1      # Single acceleration
assert sol.racecar(2) == 4      # Requires reversing
assert sol.racecar(3) == 2      # Exact power-of-two-minus-one
assert sol.racecar(4) == 5      # Overshoot then reverse
assert sol.racecar(5) == 7      # Multiple reversals
assert sol.racecar(6) == 5      # Example from prompt
assert sol.racecar(7) == 3      # Exact sequence AAA
assert sol.racecar(8) == 6      # Just beyond exact acceleration point
assert sol.racecar(9) == 8      # Requires careful backtracking
assert sol.racecar(15) == 4     # Exact power-of-two-minus-one
assert sol.racecar(16) == 7     # Slightly above exact point
assert sol.racecar(31) == 5     # Larger exact acceleration point
assert sol.racecar(100) > 0     # Larger target stress test
assert sol.racecar(1000) > 0    # Large constraint stress test
assert sol.racecar(10000) > 0   # Maximum constraint stress test

Test	Why
target = 1	Smallest valid input
target = 2	Requires reversing early
target = 3	Exact acceleration target
target = 4	Simple overshoot case
target = 5	Requires mixed strategy
target = 6	Official example
target = 7	Exact 2^k - 1 target
target = 8	Just beyond perfect acceleration
target = 9	More complicated DP structure
target = 15	Larger exact acceleration point
target = 16	Edge after exact point
target = 31	Another exact acceleration point
target = 100	Medium stress test
target = 1000	Large stress test
target = 10000	Maximum constraint validation

Edge Cases

One important edge case occurs when the target is exactly of the form:

$$2^k - 1$$

Examples include 1, 3, 7, 15, and 31. These positions can be reached using only accelerations, without any reversals. A buggy implementation might still attempt unnecessary recursive transitions. This solution handles the case immediately by checking:

if full_distance == t:

and returning k directly.

Another important edge case happens when overshooting is optimal. For example, target 6 is most efficiently solved by reaching 7 first, then reversing once. Greedy approaches that try to avoid overshooting often fail here. The DP recurrence explicitly evaluates the overshoot scenario and guarantees it is considered.

A third tricky edge case involves partial backtracking. Some targets are best solved by stopping before the target, reversing briefly, then continuing forward again. For example, certain mid range targets require a carefully balanced combination of accelerations and reversals. The loop over all possible backward acceleration counts ensures every such strategy is evaluated correctly.

Finally, large targets near 10^4 stress inefficient recursion and repeated recomputation. Without memoization, the recursive structure would become exponential. The memo table guarantees each subproblem is solved once, keeping the runtime manageable within the problem constraints.