##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2139.html

# 2139. Minimum Moves to Reach Target Score (Medium)

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`

.

**Example 1:**

Input:target = 5, maxDoubles = 0Output:4Explanation:Keep incrementing by 1 until you reach target.

**Example 2:**

Input:target = 19, maxDoubles = 2Output:7Explanation: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 = 4Output:4Explanation:Initially, x = 1 Increment once so x = 2 Double once so x = 4 Increment once so x = 5 Double again so x = 10

**Constraints:**

`1 <= target <= 10`

^{9}`0 <= maxDoubles <= 100`

**Companies**:

Wayfair

**Similar Questions**:

- Number of Steps to Reduce a Number to Zero (Easy)
- Number of Steps to Reduce a Number in Binary Representation to One (Medium)

## Solution 1. Greedy

Do doubling as late as possible so that doubling can move as many bits as possible

```
// OJ: https://leetcode.com/problems/minimum-moves-to-reach-target-score/
// Time: O(T/(2^D))
// Space: O(1)
class Solution {
public:
int minMoves(int target, int maxDoubles) {
int ans = 0;
while (target > 1) { // go from target to 1
if (target & 1) { // if the last bit is 1, increment
--target;
} else if (maxDoubles > 0) { // otherwise, if we can do doubling, do it.
--maxDoubles;
target /= 2;
} else break; // otherwise, we do all increments for the rest of steps
++ans;
}
return ans + target - 1;
}
};
```