Question

2139. Minimum Moves to Reach Target Score

中文文档

Description

You are playing a game with integers. You start with the integer 1 and you want to reach the integer target.

In one move, you can either:

• Increment the current integer by one (i.e., x = x + 1).
• Double the current integer (i.e., x = 2 * x).

You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times.

Given the two integers target and maxDoubles, return _the minimum number of moves needed to reach _target_ starting with _1.

 

Example 1:

Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.

Example 2:

Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19

Example 3:

Input: target = 10, maxDoubles = 4
Output: 4
Explanation: Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10

 

Constraints:

• 1 <= target <= 109
• 0 <= maxDoubles <= 100

Solutions

Solution 1: Backtracking + Greedy

Let's start by backtracking from the final state. Assuming the final state is $target$, we can get the previous state of $target$ as $target - 1$ or $target / 2$, depending on the parity of $target$ and the value of $maxDoubles$.

If $target=1$, no operation is needed, and we can return $0$ directly.

If $maxDoubles=0$, we can only use the increment operation, so we need $target-1$ operations.

If $target$ is even and $maxDoubles>0$, we can use the doubling operation, so we need $1$ operation, and then recursively solve $target/2$ and $maxDoubles-1$.

If $target$ is odd, we can only use the increment operation, so we need $1$ operation, and then recursively solve $target-1$ and $maxDoubles$.

The time complexity is $O(\min(\log target, maxDoubles))$, and the space complexity is $O(\min(\log target, maxDoubles))$.

We can also change the above process to an iterative way to avoid the space overhead of recursion.

class Solution:
  def minMoves(self, target: int, maxDoubles: int) -> int:
    if target == 1:
      return 0
    if maxDoubles == 0:
      return target - 1
    if target % 2 == 0 and maxDoubles:
      return 1 + self.minMoves(target >> 1, maxDoubles - 1)
    return 1 + self.minMoves(target - 1, maxDoubles)

class Solution {
  public int minMoves(int target, int maxDoubles) {
    if (target == 1) {
      return 0;
    }
    if (maxDoubles == 0) {
      return target - 1;
    }
    if (target % 2 == 0 && maxDoubles > 0) {
      return 1 + minMoves(target >> 1, maxDoubles - 1);
    }
    return 1 + minMoves(target - 1, maxDoubles);
  }
}

class Solution {
public:
  int minMoves(int target, int maxDoubles) {
    if (target == 1) {
      return 0;
    }
    if (maxDoubles == 0) {
      return target - 1;
    }
    if (target % 2 == 0 && maxDoubles > 0) {
      return 1 + minMoves(target >> 1, maxDoubles - 1);
    }
    return 1 + minMoves(target - 1, maxDoubles);
  }
};

func minMoves(target int, maxDoubles int) int {
  if target == 1 {
    return 0
  }
  if maxDoubles == 0 {
    return target - 1
  }
  if target%2 == 0 && maxDoubles > 0 {
    return 1 + minMoves(target>>1, maxDoubles-1)
  }
  return 1 + minMoves(target-1, maxDoubles)
}

function minMoves(target: number, maxDoubles: number): number {
  if (target === 1) {
    return 0;
  }
  if (maxDoubles === 0) {
    return target - 1;
  }
  if (target % 2 === 0 && maxDoubles) {
    return 1 + minMoves(target >> 1, maxDoubles - 1);
  }
  return 1 + minMoves(target - 1, maxDoubles);
}

Solution 2

class Solution:
  def minMoves(self, target: int, maxDoubles: int) -> int:
    ans = 0
    while maxDoubles and target > 1:
      ans += 1
      if target % 2 == 1:
        target -= 1
      else:
        maxDoubles -= 1
        target >>= 1
    ans += target - 1
    return ans

class Solution {
  public int minMoves(int target, int maxDoubles) {
    int ans = 0;
    while (maxDoubles > 0 && target > 1) {
      ++ans;
      if (target % 2 == 1) {
        --target;
      } else {
        --maxDoubles;
        target >>= 1;
      }
    }
    ans += target - 1;
    return ans;
  }
}

class Solution {
public:
  int minMoves(int target, int maxDoubles) {
    int ans = 0;
    while (maxDoubles > 0 && target > 1) {
      ++ans;
      if (target % 2 == 1) {
        --target;
      } else {
        --maxDoubles;
        target >>= 1;
      }
    }
    ans += target - 1;
    return ans;
  }
};

func minMoves(target int, maxDoubles int) (ans int) {
  for maxDoubles > 0 && target > 1 {
    ans++
    if target&1 == 1 {
      target--
    } else {
      maxDoubles--
      target >>= 1
    }
  }
  ans += target - 1
  return
}

function minMoves(target: number, maxDoubles: number): number {
  let ans = 0;
  while (maxDoubles && target > 1) {
    ++ans;
    if (target & 1) {
      --target;
    } else {
      --maxDoubles;
      target >>= 1;
    }
  }
  ans += target - 1;
  return ans;
}