Leetcode 2139: Minimum Moves to Reach Target Score

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