Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

818. Race Car

Time: $O(|\texttt{target}|)$

Space: $O(|\texttt{target}|)$

			


class Solution {
 public:
  int racecar(int target) {
    dp.resize(target + 1, -1);
    return rc(target);
  }

 private:
  vector<int> dp;

  int rc(int i) {
    if (dp[i] >= 0)
      return dp[i];

    int ans = 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) + rc(i - (j - k))
    for (; j < i; j = (1 << ++x) - 1)
      for (int y = 0, k = 0; k < j; k = (1 << ++y) - 1)
        ans = min(ans, (x + 1) + (y + 1) + rc(i - (j - k)));

    // XA || (xA + 1R) + rc(j - i)
    ans = min(ans, i == j ? x : x + 1 + rc(j - i));
    return dp[i] = ans;
  }
};




			


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

  private int[] dp;

  private int rc(int i) {
    if (dp[i] >= 0)
      return dp[i];

    int ans = 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) + rc(i - (j - k))
    for (; j < i; j = (1 << ++x) - 1)
      for (int y = 0, k = 0; k < j; k = (1 << ++y) - 1)
        ans = Math.min(ans, (x + 1) + (y + 1) + rc(i - (j - k)));

    // XA || (xA + 1R) + rc(j - i)
    ans = Math.min(ans, i == j ? x : x + 1 + rc(j - i));
    return dp[i] = ans;
  }
}