##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/818.html

# 818. Race Car

Hard

## Description

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction “A”, your car does the following: position += speed, speed *= 2.

When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1, otherwise speed = 1. (Your position stays the same.)

For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:

Input:

target = 3

Output: 2

Explanation:

The shortest instruction sequence is “AA”.

Example 2:

Input:

target = 6

Output: 5

Explanation:

The shortest instruction sequence is “AAARA”.

Note:

• 1 <= target <= 10000.

## Solution

Use dynamic programming. Create an array dp of length Math.max(target + 3, target * 2), where dp[i] represents the length of the shortest sequence of instructions to get to position i. Initialize dp = 0, dp = 1 and dp = 4.

If i is 2^k - 1 for some k, then dp[i] = k. Otherwise, suppose 2^(k - 1) <= i < 2^k for some positive integer k, it is possible to reach 2^(k - 1) - 1 first and then use instructions with “R” to reach i, or reach 2^k - 1 first and then use instructions with “R” to reach i. Calculate the minimum length accordingly.

• class Solution {
public int racecar(int target) {
int[] dp = new int[Math.max(target + 3, target * 2)];
Arrays.fill(dp, Integer.MAX_VALUE);
dp = 0;
dp = 1;
dp = 4;
for (int i = 3; i <= target; i++) {
int bits = (int) (Math.log(i) / Math.log(2)) + 1;
if (i == (1 << bits) - 1)
dp[i] = bits;
else {
for (int j = 0; j < bits - 1; j++)
dp[i] = Math.min(dp[i], dp[i - (1 << (bits - 1)) + (1 << j)] + bits - 1 + j + 2);
if ((1 << bits) - 1 - i < i)
dp[i] = Math.min(dp[i], dp[(1 << bits) - 1 - i] + bits + 1);
}
}
return dp[target];
}
}

• // OJ: https://leetcode.com/problems/race-car/
// Time: O(?)
// Space: O(?)
// Ref: https://leetcode.com/problems/race-car/discuss/124312/Javascript-Python3-C%2B%2B-.-BFS-solutions
class Solution {
public:
int racecar(int target) {
queue<array<int, 2>> q;
q.push({0, 1});
unordered_map<int, unordered_set<int>> seen;
seen.insert(1);
int step = 0;
while (true) {
int cnt = q.size();
while (cnt--) {
auto [pos, speed] = q.front();
q.pop();
if (pos == target) return step;
vector<array<int, 2>> cand;
if (abs(target - (pos + speed)) < target) cand.push_back({ pos + speed, 2 * speed }); // Only continue moving in the current direction if doing so reduces the distance.
cand.push_back({ pos, speed < 0 ? 1 : - 1 }); // reverse direction
for (auto &[pos, speed] : cand) {
if (seen[pos].count(speed)) continue;
seen[pos].insert(speed);
q.push({pos, speed});
}
}
++step;
}
return -1;
}
};

• class Solution:
def racecar(self, target: int) -> int:
dp =  * (target + 1)
for i in range(1, target + 1):
k = i.bit_length()
if i == 2**k - 1:
dp[i] = k
continue
dp[i] = dp[2**k - 1 - i] + k + 1
for j in range(k - 1):
dp[i] = min(dp[i], dp[i - (2 ** (k - 1) - 2**j)] + k - 1 + j + 2)
return dp[target]


• func racecar(target int) int {
dp := make([]int, target+1)
for i := 1; i <= target; i++ {
k := bits.Len(uint(i))
if i == (1<<k)-1 {
dp[i] = k
continue
}
dp[i] = dp[(1<<k)-1-i] + k + 1
for j := 0; j < k; j++ {
dp[i] = min(dp[i], dp[i-(1<<(k-1))+(1<<j)]+k-1+j+2)
}
}
return dp[target]
}

func min(a, b int) int {
if a < b {
return a
}
return b
}