LeetCode 2139 - Minimum Moves to Reach Target Score

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

The problem asks us to transform the integer 1 into the integer target using the minimum number of moves. At every move, we are allowed to perform one of two operations:

Increment the current number by 1
Double the current number

The important restriction is that the doubling operation can only be used at most maxDoubles times. Increment operations have no limit.

The input consists of two integers:

target, the value we want to reach
maxDoubles, the maximum number of times we are allowed to use the doubling operation

The output is a single integer representing the minimum number of moves required to reach target starting from 1.

The constraints are important:

target can be as large as 10^9
maxDoubles can be at most 100

A naive breadth first search or dynamic programming solution over all values from 1 to target would be too expensive when target is extremely large. We need an approach that works in logarithmic time rather than linear time.

One key observation is that doubling is extremely powerful because it increases the value much faster than incrementing. Therefore, an optimal solution should use doubling strategically whenever it saves moves.

Several edge cases are important:

When maxDoubles = 0, we can only increment, so the answer is simply target - 1
When target = 1, we are already at the target, so the answer is 0
When the target becomes odd during reverse processing, we cannot directly halve it, so we must subtract one first
When we run out of doubling operations, the remaining distance must be covered entirely with increments

Approaches

Brute Force Approach

A straightforward idea is to model the problem as a shortest path search. Starting from 1, we can repeatedly generate the next states:

x + 1
2 * x, if we still have remaining doubles

We could use breadth first search because each operation costs exactly one move.

This approach is correct because BFS guarantees that the first time we reach target, we have used the minimum number of operations.

However, this approach is far too slow for the given constraints. The search space can grow very large because target may be up to 10^9. Even storing visited states becomes impractical.

Another brute force possibility is recursive backtracking or dynamic programming over states (currentValue, remainingDoubles), but that also becomes infeasible for large targets.

Optimal Greedy Approach

The key insight is that working backward from target to 1 is much easier than building upward.

Instead of asking:

"How do we build target from 1?"

We ask:

"How do we reduce target back to 1?"

In reverse:

Increment becomes decrement
Double becomes divide by 2

This reverse perspective leads to a greedy strategy:

If the current target is even and we still have doubling operations available, dividing by 2 is always optimal because it reduces the number much faster than repeated decrements.
If the current target is odd, we must subtract 1 first because odd numbers cannot be divided evenly by 2.
If we run out of doubling operations, the only remaining option is to decrement until we reach 1.

This approach is efficient because each division by 2 dramatically reduces the number, leading to logarithmic complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(target) or worse	O(target)	Explores many states, infeasible for large target
Optimal Greedy	O(log target)	O(1)	Works backward greedily using division

Algorithm Walkthrough

Initialize a variable moves to 0.
While target is greater than 1 and we still have remaining doubles, repeatedly reduce the target.
If target is even, divide it by 2.

This corresponds to reversing a doubling operation. Since division shrinks the number rapidly, it is always beneficial when available. 4. If target is odd, subtract 1.

An odd number cannot be divided evenly by 2, so we must first make it even. 5. After every operation, increment the move counter. 6. Decrease maxDoubles whenever we perform a division by 2, because this corresponds to consuming one doubling operation in the forward direction. 7. Eventually, either:

target becomes 1, or
we run out of doubling operations

If we run out of doubles and target is still greater than 1, the only possible moves are decrements. Since going from target to 1 requires exactly target - 1 decrements, add that directly to the answer.
Return the total number of moves.

Why it works

The greedy choice is optimal because division by 2 provides the largest possible reduction in value with a single operation. Whenever division is available, delaying it would only require additional decrement operations later.

When the number is odd, subtracting one is mandatory because division is impossible. Therefore, every greedy step is forced or strictly optimal, guaranteeing the minimum number of moves.

Python Solution

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        moves = 0

        while target > 1 and maxDoubles > 0:
            if target % 2 == 0:
                target //= 2
                maxDoubles -= 1
            else:
                target -= 1

            moves += 1

        if target > 1:
            moves += target - 1

        return moves

The implementation follows the reverse greedy strategy directly.

The variable moves keeps track of the total number of operations performed.

The while loop continues as long as two conditions are true:

target > 1
we still have doubling operations available

Inside the loop:

If the target is even, we divide by 2 and consume one doubling operation.
If the target is odd, we subtract 1 to make it even.

Each action counts as one move.

After the loop finishes, we may still have a target larger than 1. At this point, no doubling operations remain, so the only possible action is decrementing repeatedly. Instead of simulating each decrement individually, we add target - 1 directly.

Finally, the function returns the accumulated move count.

Go Solution

func minMoves(target int, maxDoubles int) int {
    moves := 0

    for target > 1 && maxDoubles > 0 {
        if target%2 == 0 {
            target /= 2
            maxDoubles--
        } else {
            target--
        }

        moves++
    }

    if target > 1 {
        moves += target - 1
    }

    return moves
}

The Go implementation mirrors the Python solution closely.

Go uses integer division automatically for integer types, so target /= 2 behaves exactly as expected.

No special handling for overflow is needed because the constraints remain well within Go's standard integer range.

The algorithm uses constant extra memory because only a few integer variables are maintained.

Worked Examples

Example 1

Input:

target = 5
maxDoubles = 0

Since no doubling operations are allowed, we can only increment.

Step	Current Target	maxDoubles	Action	Moves
Start	5	0	No doubles available	0
Final	1	0	Use 4 decrements	4

Answer: 4

Example 2

Input:

target = 19
maxDoubles = 2

We process backward from 19 to 1.

Step	Current Target	maxDoubles	Action	Moves
Start	19	2	Odd, subtract 1	1
2	18	2	Even, divide by 2	2
3	9	1	Odd, subtract 1	3
4	8	1	Even, divide by 2	4
End Loop	4	0	No doubles left	4
Final	1	0	Add 3 decrements	7

Answer: 7

Example 3

Input:

target = 10
maxDoubles = 4

Step	Current Target	maxDoubles	Action	Moves
Start	10	4	Even, divide by 2	1
2	5	3	Odd, subtract 1	2
3	4	3	Even, divide by 2	3
4	2	2	Even, divide by 2	4
End	1	1	Done	4

Answer: 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log target)	Each division by 2 reduces the number significantly
Space	O(1)	Only a few integer variables are used

The algorithm is extremely efficient because every division operation cuts the target roughly in half. Since a number can only be halved logarithmically many times, the loop runs at most O(log target) iterations.

The space complexity is constant because no additional data structures are allocated.

Test Cases

sol = Solution()

assert sol.minMoves(5, 0) == 4  # no doubling allowed
assert sol.minMoves(19, 2) == 7  # example with mixed operations
assert sol.minMoves(10, 4) == 4  # example with sufficient doubles

assert sol.minMoves(1, 0) == 0  # already at target
assert sol.minMoves(1, 10) == 0  # target already reached even with doubles

assert sol.minMoves(2, 1) == 1  # single doubling
assert sol.minMoves(2, 0) == 1  # single increment

assert sol.minMoves(100, 0) == 99  # only increments possible
assert sol.minMoves(100, 10) == 8  # many useful doubles

assert sol.minMoves(999999999, 100) > 0  # large target stress test
assert sol.minMoves(16, 4) == 4  # repeated doubling path
assert sol.minMoves(15, 4) == 6  # odd numbers require decrement first

Test	Why
`minMoves(5, 0)`	Validates behavior with no doubling
`minMoves(19, 2)`	Tests mixed odd and even transitions
`minMoves(10, 4)`	Tests efficient use of doubling
`minMoves(1, 0)`	Smallest possible target
`minMoves(1, 10)`	Ensures immediate return when already at target
`minMoves(2, 1)`	Simplest doubling case
`minMoves(2, 0)`	Simplest increment-only case
`minMoves(100, 0)`	Large increment-only scenario
`minMoves(100, 10)`	Verifies greedy halving behavior
`minMoves(999999999, 100)`	Stress test for large target
`minMoves(16, 4)`	Pure powers of two
`minMoves(15, 4)`	Multiple odd-number transitions

Edge Cases

One important edge case occurs when maxDoubles = 0. In this situation, division operations are impossible in the reverse process, meaning the only valid action is repeated decrementing. A naive implementation might still attempt unnecessary loop logic, but this solution immediately falls through to the final addition of target - 1.

Another critical edge case is when target = 1. Since we already begin at 1, the answer should be 0. Some implementations accidentally perform extra operations or enter loops unnecessarily. This solution avoids that because the main loop condition requires target > 1.

Odd targets are another common source of bugs. An odd number cannot be evenly divided by 2, so subtracting one first is mandatory. Forgetting this detail can produce incorrect move counts or invalid states. The implementation explicitly checks parity before dividing.

A final subtle case happens when doubling operations run out before reaching 1. At that point, decrementing is the only remaining option. Instead of simulating every decrement one by one, the algorithm adds target - 1 directly, which preserves correctness while remaining efficient.