Minimum Moves to Reach Target Score
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, but 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 = 0Output
4Since no double operations are allowed, you must increment four times to reach 5 from 1.
Example 2
Input
target = 19, maxDoubles = 2Output
7Using two doubles optimally, one sequence is increment three times to 4, double to 8, increment to 9, double to 18, then increment to 19 for 7 moves.
Constraints
- 1 <= target <= 10^9
- 0 <= maxDoubles <= 100