# 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:Incrementthe current integer by one (i.e.,`x = x + 1`

).Doublethe current integer (i.e.,`x = 2 * x`

).You can use the

incrementoperationanynumber of times, however, you can only use thedoubleoperationat most`maxDoubles`

times.

Given the two integers`target`

and`maxDoubles`

, returnthe 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.

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

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 :)