#2139
Minimum Moves to Reach Target Score
specialist · 830 · lc medium +31 · verified · 52.3% accepted · 1,086 likes · top 42%
Description
You are playing a number game. You begin at 1 and want to reach the integer target.
Each move lets you either:
- Add 1 to the current value (i.e., x = x + 1).
- Double the current value (i.e., x = 2 * x).
The increment operation may be used without limit, but the doubling operation can be used at most maxDoubles times.
Given target and maxDoubles, return the minimum total number of moves to reach target starting from 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
Code
1
2
3