Minimum Moves to Reach Target Score — Medium Problem & Solution

Problem statement

You start at 1 and want to reach target. Each move either increments the value by 1, or doubles it — and doubling may be used at most maxDoubles times in total.

Return the minimum number of moves.

Example 1

Input: target = 5, maxDoubles = 0
Output: 4
Explanation: With no doubling available, only increments work: 1 → 2 → 3 → 4 → 5.

Example 2

Input: target = 19, maxDoubles = 2
Output: 7
Explanation: 1 → 2 → 3 → 4 → 8 → 9 → 18 → 19 uses both doublings.

Example 3

Input: target = 10, maxDoubles = 4
Output: 4
Explanation: 1 → 2 → 4 → 5 → 10.

Constraints

• 1 <= target <= 1000000000
• 0 <= maxDoubles <= 100

How to solve Minimum Moves to Reach Target Score

Reversing the process removes the choice. Going down from target, an odd value must have been reached by an increment, and an even value is best reached by a doubling — halving shrinks the number far faster than decrementing.

Approach

1. While the value exceeds 1: if no doublings remain, add value - 1 moves and stop.
2. If the value is odd, subtract 1 and count a move.
3. Otherwise halve it, spend a doubling and count a move.

Why it works

Halving an even v costs one move and removes v/2 units of distance, whereas decrementing costs one move and removes 1 — so while doublings remain, halving dominates. Odd values leave no choice at all. Once the budget is gone the remaining distance can only be covered one increment at a time.

Complexity

• Time — O(log target)
• Space — O(1)

Pitfalls

• Working forwards means guessing where to spend the doublings; backwards the moves are forced.
• Forgetting to stop once maxDoubles hits zero makes the loop halve for free.
• target = 1 needs zero moves — the loop condition must be > 1.

Reference solution

Python

def minMoves(target: int, maxDoubles: int) -> int:
    moves = 0
    while target > 1:
        if maxDoubles == 0:
            return moves + target - 1
        if target % 2 == 1:
            target -= 1
        else:
            target //= 2
            maxDoubles -= 1
        moves += 1
    return moves

JavaScript

var minMoves = function(target, maxDoubles) {
    var moves = 0, v = target, doubles = maxDoubles;
    while (v > 1) {
        if (doubles === 0) return moves + v - 1;
        if (v % 2 === 1) v -= 1;
        else { v = v / 2; doubles--; }
        moves++;
    }
    return moves;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Find the Winner of the Circular Game Medium
• Stone Game VII Medium
• Number of Ways to Divide a Long Corridor Medium
• Count Ways to Group Overlapping Ranges Medium
• Count Number of Ways to Place Houses Medium
• Count Number of Texts Medium