Leetcode 2139: Minimum Moves to Reach Target Score

Pierre-Marie Poitevin
3 min readJan 18, 2022

In this exercise, we are trying to obtain a target number using +1 and *2 operations, we also have a limited number of *2 operations:

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.

To solve this problem, we can figure out the solution by using a couple of observations:

  • A double operation is only used to obtain an even number
  • It is more efficient to use the double operations at the end, because that’s when the doubling is doing the most

That is very useful to obtain out algorithm afterwards. If we go from the target to 1, then the operations are reversed to -1 and /2, and we do /2 each time we can, that is when we have an even number, and we still have remaining double operations.

For instance with target 19 and maxDoubles = 2

19 = 1 + 18
= 1 + 2 * 9
= 1 + 2 * (1 + 8)
= 1 + 2 * (1 + 2 * 4)
= 1 + 2 * (1 + 2 * (1 + 1 + 1 + 1))
1 1 1 1 1 1 1 => 7 operations

Each time we have an even number like 18 or 8, we divide by 2. With 4, we didn’t have any double operations leftover, so we had to resolve it with 3 +1 operations.

Optimal solution for target 19 and maxDoubles 2

We write the algorithm recursively by handling the following cases:

  • If target is 1, return 0
  • If maxDoubles is 0, return target — 1
  • If target is odd, solve the same problem with target-1 and add 1 to that result
  • Otherwise, solve the problem with target/2 and maxDoubles-1 and add 1 to that result
Recursive algorithms

This is the code I obtained in Java:

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

Happy coding :)

--

--