818. Race Car LeetCode Solution

Last updated: February 20, 2025

In this guide, you will get 818. Race Car LeetCode Solution with the best time and space complexity. The solution to Race Car problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Race Car solution in C++
Race Car solution in Java
Race Car solution in Python
Additional Resources

Problem Statement of 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

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.
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

Complexity Analysis

Time Complexity: O(|\texttt{target}|)
Space Complexity: O(|\texttt{target}|)

818. Race Car LeetCode Solution in C++

class Solution {
 public:
  int racecar(int target) {
    vector<int> mem(target + 1, -1);
    return racecar(target, mem);
  }

 private:
  int racecar(int i, vector<int>& mem) {
    if (mem[i] >= 0)
      return mem[i];

    int res = INT_MAX;
    int x = 1;             // xA := (2^x - 1) unit distance
    int j = (1 << x) - 1;  // j = 2^x - 1, k = 2^y - 1

    // (xA + 1R) + (yA + 1R) + racecar(i - (j - k))
    for (; j < i; j = (1 << ++x) - 1)
      for (int y = 0, k = 0; k < j; k = (1 << ++y) - 1)
        res = min(res, (x + 1) + (y + 1) + racecar(i - (j - k), mem));

    // xA || (xA + 1R) + racecar(j - i)
    return mem[i] = min(res, i == j ? x : x + 1 + racecar(j - i, mem));
  }
};
/* code provided by PROGIEZ */

818. Race Car LeetCode Solution in Java

class Solution {
  public int racecar(int target) {
    int[] mem = new int[target + 1];
    Arrays.fill(mem, -1);
    return racecar(target, mem);
  }

  private int racecar(int i, int[] mem) {
    if (mem[i] >= 0)
      return mem[i];

    int res = Integer.MAX_VALUE;
    int x = 1;            // xA := (2^x - 1) unit distance
    int j = (1 << x) - 1; // j = 2^x - 1, k = 2^y - 1

    // (xA + 1R) + (yA + 1R) + racecar(i - (j - k))
    for (; j < i; j = (1 << ++x) - 1)
      for (int y = 0, k = 0; k < j; k = (1 << ++y) - 1)
        res = Math.min(res, (x + 1) + (y + 1) + racecar(i - (j - k), mem));

    // xA || (xA + 1R) + racecar(j - i)
    return mem[i] = Math.min(res, i == j ? x : x + 1 + racecar(j - i, mem));
  }
}
// code provided by PROGIEZ

818. Race Car LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents