#2139

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Moves to Reach Target Score

Calculate the fewest steps to reach a target integer using increments and limited doubles with a greedy strategy.

Problem Statement

You start a game with the integer 1 and aim to reach a given target integer. Each move can either increment the current value by 1 or double the value, but doubling is restricted to maxDoubles times.

Determine the minimum number of moves needed to reach the target value. You can use increments any number of times, but you must carefully plan double operations to minimize total moves while adhering to the limit.

Examples

Example 1

Input: target = 5, maxDoubles = 0

Output: 4

Keep incrementing by 1 until you reach target.

Example 2

Input: target = 19, maxDoubles = 2

Output: 7

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

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 <= 109
0 <= maxDoubles <= 100

Solution Approach

Reverse Greedy Strategy

Instead of building up from 1, start from the target and work backward toward 1. At each step, halve the target if remaining doubles allow, otherwise decrement by 1. This approach guarantees the fewest moves by applying doubles optimally and avoids wasted increments.

Counting Moves Efficiently

Maintain a counter for total moves while reducing the target. When the target is odd, decrement first to make it even before halving. Repeat until reaching 1. This stepwise counting directly maps to the minimum moves required, respecting the maxDoubles limit.

Greedy Choice Justification

The key invariant is that using a double whenever possible is always optimal for reducing future increments. Any deviation from halving when allowed results in additional steps. This pattern ensures minimal moves and is central to the problem's greedy choice plus invariant validation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log target) because each halving reduces the number substantially, and space complexity is O(1) since only counters and variables are needed. Using the reverse approach avoids extra storage.

What Interviewers Usually Probe

Check if the candidate recognizes that working backward simplifies the greedy decision.
Listen for correct handling of odd target values before doubling.
Verify the candidate counts moves while respecting maxDoubles constraint.

Common Pitfalls or Variants

Common pitfalls

Attempting to always double without checking remaining maxDoubles may overshoot minimal moves.
Incrementing forward from 1 without considering reverse halving strategy leads to unnecessary steps.
Failing to handle odd targets correctly before halving can increase move count.

Follow-up variants

Allow multiple doubling operations per move and adjust the greedy logic accordingly.
Change the starting integer from 1 to any positive integer, requiring modified backward calculations.
Limit total moves instead of doubles and ask whether reaching target is possible.

FAQ

What is the main strategy for Minimum Moves to Reach Target Score?

The optimal strategy is reverse greedy: start at the target, decrement if odd, halve if even and doubles remain, counting moves until reaching 1.

Why does working backward simplify this problem?

It ensures that every double operation is applied at the most beneficial step, avoiding unnecessary increments and minimizing total moves.

How do odd numbers affect move calculation?

When the target is odd, you must decrement before halving to maintain integer values, ensuring the greedy invariant holds.

Can the solution handle very large target values efficiently?

Yes, because halving reduces the target logarithmically, the reverse greedy approach remains fast even for large targets up to 10^9.

What is the failure mode if maxDoubles is ignored?

Ignoring maxDoubles can result in attempting impossible double operations, causing overestimation of progress and incorrect minimal moves.

terminal

Solution

Solution 1: Backtracking + Greedy

Let's start by backtracking from the final state. Assuming the final state is $target$, we can get the previous state of $target$ as $target - 1$ or $target / 2$, depending on the parity of $target$ and the value of $maxDoubles$.

1

2

3

4

5

6

7

8

9

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        if target == 1:
            return 0
        if maxDoubles == 0:
            return target - 1
        if target % 2 == 0 and maxDoubles:
            return 1 + self.minMoves(target >> 1, maxDoubles - 1)
        return 1 + self.minMoves(target - 1, maxDoubles)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        if target == 1:
            return 0
        if maxDoubles == 0:
            return target - 1
        if target % 2 == 0 and maxDoubles:
            return 1 + self.minMoves(target >> 1, maxDoubles - 1)
        return 1 + self.minMoves(target - 1, maxDoubles)

Continue Practicing

#2160 minimum sum of four digit number after splitting digits #2178 maximum split of positive even integers #2195 append k integers with minimal sum