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.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
Solution 2
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|