## Algorithm

Problem Name: 818. Race Car

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`

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

Given a target position `target`, return 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".
Your position goes from 0 --> 1 --> 3.
```

Example 2:

```Input: target = 6
Output: 5
Explanation:
The shortest instruction sequence is "AAARA".
Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.
```

Constraints:

• `1 <= target <= 104`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
const racecar = function (target) {
const dp = new Array(target + 1).fill(0)
for (let i = 1; i  < = target; i++) {
dp[i] = Number.MAX_VALUE
let m = 1,
j = 1
for (; j  <  i; j = (1 << ++m) - 1) {
for (let q = 0, p = 0; p  <  j; p = (1 << ++q) - 1) {
dp[i] = Math.min(dp[i], m + 1 + q + 1 + dp[i - (j - p)])
}
}
dp[i] = Math.min(dp[i], m + (i == j ? 0 : 1 + dp[j - i]))
}
return dp[target]
}
``````
Copy The Code &

Input

cmd
target = 3

Output

cmd
2

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def racecar(self, target):
q, cnt, used = [(0, 1)], 0, {(0, 1)}
while q:
new = []
for pos, speed in q:
if pos == target:
return cnt
elif pos > 20000 or -20000 > pos:
continue
if (pos + speed, speed * 2) not in used:
new.append((pos + speed, speed * 2))
used.add((pos + speed, speed * 2))
if speed > 0 and (pos, -1) not in used:
new.append((pos, -1))
elif speed < 0 and (pos, 1) not in used:
new.append((pos, 1))
q = new
cnt += 1
``````
Copy The Code &

Input

cmd
target = 3

Output

cmd
2

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0818_RaceCar
{
private const int INT_BITS = sizeof(int) * 8; // compile time constant

public int Racecar(int target)
{
var dp = new int[target + 1];
for (int i = 1; i  < = target; i++)
dp[i] = int.MaxValue;
dp[0] = 0;

for (int i = 1; i  < = target; i++)
{
var k = INT_BITS - GetLeadingZeros(i);
if ((1 << k) - 1 == i)
{
dp[i] = k;
continue;
}

for (int q = 0; q  <  k - 1; q++)
dp[i] = Math.Min(dp[i], k + q + 1 + dp[i - ((1 << (k - 1)) - (1 << q))]);

if ((1 << k) - 1 - i  <  i)
dp[i] = Math.Min(dp[i], k + 1 + dp[(1 << k) - 1 - i]);
}

return dp[target];
}

{
// do the smearing
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
// count the ones
x -= x >> 1 & 0x55555555;
x = (x >> 2 & 0x33333333) + (x & 0x33333333);
x = (x >> 4) + x & 0x0f0f0f0f;
x += x >> 8;
x += x >> 16;
return INT_BITS - (x & 0x0000003f); // subtract # of 1s from 32
}
}
}
``````
Copy The Code &

Input

cmd
target = 6

Output

cmd
5