Race Car
Race Car is a hard dynamic programming problem solved with the 1d dp pattern.
The best approach, optimal (dp on distance), runs in O(T log T) time and O(T) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs over position and speed) up.
Problem
A car sits at position 0 on an endless number line with speed +1. It obeys two instructions:
A(accelerate):position += speed, thenspeed *= 2.R(reverse): the speed becomes-1if it was positive, otherwise+1. The position does not change.
Given a positive integer target, return the length of the shortest instruction string that leaves the car at exactly target.
Examples
Example 1
- Input
target = 7- Output
3- Why
- "AAA" moves the car 1 + 2 + 4 = 7, ending exactly on 7.
Example 2
- Input
target = 5- Output
7- Why
- "AARARAA": reach 3, turn, back up to 2, turn again, then two A's go 2 -> 3 -> 5. No shorter string ends on 5.
Example 3
- Input
target = 2- Output
4- Why
- "AARA" goes to 3, turns, and steps back to 2.
Constraints
1 <= target <= 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (BFS over position and speed) | O(T log T) | O(T log T) |
| Optimal (DP on distance) | O(T log T) | O(T) |
1Brute force (BFS over position and speed)
O(T log T)Positions are limited to about 4T values and speeds to about log T powers of two in each direction, and each state is processed once.O(T log T)The visited set and queue can hold every reachable state.Treat (position, speed) as a graph node. A and R are the two edges out of every node, each of cost 1, so a breadth-first search from (0, 1) finds the fewest instructions. Positions far beyond the target are never useful, so they are pruned.
- Start a queue with (0, 1) and a visited set.
- Process the queue level by level; the level number is the instruction count.
- If the position equals the target, return the level.
- Accelerate: (pos + speed, speed * 2), kept only if |new pos| <= 2 * target.
- Reverse: (pos, -1 if speed > 0 else 1).
- Add each unseen state to the queue.
class Solution {
public int racecar(int target) {
Deque<int[]> queue = new ArrayDeque<>();
Set<Long> seen = new HashSet<>();
queue.add(new int[] { 0, 1 });
seen.add(key(0, 1));
int steps = 0;
while (!queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
int[] cur = queue.poll();
int pos = cur[0], speed = cur[1];
if (pos == target) return steps;
int np = pos + speed, ns = speed * 2;
if (Math.abs(np) <= 2 * target && seen.add(key(np, ns))) {
queue.add(new int[] { np, ns });
}
int rs = speed > 0 ? -1 : 1;
if (seen.add(key(pos, rs))) {
queue.add(new int[] { pos, rs });
}
}
steps++;
}
return -1;
}
private long key(int pos, int speed) {
return (long) pos * 1_000_000L + speed;
}
}class Solution:
def racecar(self, target: int) -> int:
queue = deque([(0, 1)])
seen = {(0, 1)}
steps = 0
while queue:
for _ in range(len(queue)):
pos, speed = queue.popleft()
if pos == target:
return steps
np, ns = pos + speed, speed * 2
if abs(np) <= 2 * target and (np, ns) not in seen:
seen.add((np, ns))
queue.append((np, ns))
rs = -1 if speed > 0 else 1
if (pos, rs) not in seen:
seen.add((pos, rs))
queue.append((pos, rs))
steps += 1
return -1class Solution {
public:
int racecar(int target) {
queue<pair<int, int>> q;
unordered_set<long long> seen;
auto key = [](int pos, int speed) { return (long long)pos * 1000000LL + speed; };
q.push({0, 1});
seen.insert(key(0, 1));
int steps = 0;
while (!q.empty()) {
for (int size = q.size(); size > 0; size--) {
auto [pos, speed] = q.front();
q.pop();
if (pos == target) return steps;
int np = pos + speed, ns = speed * 2;
if (abs(np) <= 2 * target && seen.insert(key(np, ns)).second) {
q.push({np, ns});
}
int rs = speed > 0 ? -1 : 1;
if (seen.insert(key(pos, rs)).second) {
q.push({pos, rs});
}
}
steps++;
}
return -1;
}
};function racecar(target) {
const key = (pos, speed) => pos * 1000000 + speed;
let queue = [[0, 1]];
const seen = new Set([key(0, 1)]);
let steps = 0;
while (queue.length > 0) {
const next = [];
for (const [pos, speed] of queue) {
if (pos === target) return steps;
const np = pos + speed, ns = speed * 2;
if (Math.abs(np) <= 2 * target && !seen.has(key(np, ns))) {
seen.add(key(np, ns));
next.push([np, ns]);
}
const rs = speed > 0 ? -1 : 1;
if (!seen.has(key(pos, rs))) {
seen.add(key(pos, rs));
next.push([pos, rs]);
}
}
queue = next;
steps++;
}
return -1;
}2Optimal (DP on distance)
O(T log T)Each of the T distances tries at most log T values of m.O(T)One dp array of size T + 1.Let dp[t] be the fewest instructions to cover distance t starting at speed 1. If t has k bits, k A's reach 2^k - 1. If that is exactly t, the answer is k. Otherwise either overshoot to 2^k - 1, reverse, and cover the leftover 2^k - 1 - t (which is a fresh problem from speed 1), or stop at 2^(k-1) - 1, reverse, back up 2^m - 1 with m A's, reverse again, and cover what remains forwards. Every leftover distance is smaller than t.
- For t from 1 to target, let k be the bit length of t.
- If t == 2^k - 1, dp[t] = k.
- Otherwise start with dp[t] = k + 1 + dp[2^k - 1 - t] (overshoot, reverse).
- For each m from 0 to k - 2, try (k - 1) + 1 + m + 1 + dp[t - (2^(k-1) - 1) + (2^m - 1)].
- Return dp[target].
class Solution {
public int racecar(int target) {
int[] dp = new int[target + 1];
for (int t = 1; t <= target; t++) {
int k = 32 - Integer.numberOfLeadingZeros(t);
if (t == (1 << k) - 1) {
dp[t] = k;
continue;
}
dp[t] = k + 1 + dp[(1 << k) - 1 - t];
for (int m = 0; m < k - 1; m++) {
int rest = t - ((1 << (k - 1)) - 1) + ((1 << m) - 1);
dp[t] = Math.min(dp[t], (k - 1) + 1 + m + 1 + dp[rest]);
}
}
return dp[target];
}
}class Solution:
def racecar(self, target: int) -> int:
dp = [0] * (target + 1)
for t in range(1, target + 1):
k = t.bit_length()
if t == (1 << k) - 1:
dp[t] = k
continue
best = k + 1 + dp[(1 << k) - 1 - t]
for m in range(k - 1):
rest = t - ((1 << (k - 1)) - 1) + ((1 << m) - 1)
best = min(best, (k - 1) + 1 + m + 1 + dp[rest])
dp[t] = best
return dp[target]class Solution {
public:
int racecar(int target) {
vector<int> dp(target + 1, 0);
for (int t = 1; t <= target; t++) {
int k = 32 - __builtin_clz(t);
if (t == (1 << k) - 1) {
dp[t] = k;
continue;
}
dp[t] = k + 1 + dp[(1 << k) - 1 - t];
for (int m = 0; m < k - 1; m++) {
int rest = t - ((1 << (k - 1)) - 1) + ((1 << m) - 1);
dp[t] = min(dp[t], (k - 1) + 1 + m + 1 + dp[rest]);
}
}
return dp[target];
}
};function racecar(target) {
const dp = new Array(target + 1).fill(0);
for (let t = 1; t <= target; t++) {
const k = 32 - Math.clz32(t);
if (t === (1 << k) - 1) {
dp[t] = k;
continue;
}
dp[t] = k + 1 + dp[(1 << k) - 1 - t];
for (let m = 0; m < k - 1; m++) {
const rest = t - ((1 << (k - 1)) - 1) + ((1 << m) - 1);
dp[t] = Math.min(dp[t], (k - 1) + 1 + m + 1 + dp[rest]);
}
}
return dp[target];
}Edge cases to test
- Targets of the form 2^k - 1 (1, 3, 7, 15...), reached with only A's
- Targets just past 2^k - 1, where overshooting and coming back competes with stopping early
- target = 1
Hints
Hint 1
Each state of the car is just its position and its speed. Every instruction costs 1, so the shortest sequence is a shortest path.
Hint 2
After k A's from speed 1 the car has moved 2^k - 1. For a target t with k bits, either drive to 2^k - 1 (past t) and solve the rest backwards, or stop at 2^(k-1) - 1, turn, back up a little, turn again and solve the rest forwards.
Hint 3
Both options leave a smaller distance to cover, so dp[t] can be built from dp of smaller values.
FAQ
What is the best time complexity for Race Car?
Optimal (DP on distance) runs in O(T log T) time and O(T) extra space. Each of the T distances tries at most log T values of m.
Which pattern does Race Car use?
It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).
Is there a brute force solution for Race Car?
Yes. Brute force (BFS over position and speed) takes O(T log T) time and O(T log T) space. Treat (position, speed) as a graph node.
Which edge cases should I test for Race Car?
Targets of the form 2^k - 1 (1, 3, 7, 15...), reached with only A's; Targets just past 2^k - 1, where overshooting and coming back competes with stopping early; target = 1.