Minimum Moves to Reach Target Score

Medium
709.

Minimum Moves to Reach Target Score

Minimum Moves to Reach Target Score is a medium coding problem on math and greedy, asked in Amazon, Google and Walmart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} target
 * @param {number} maxDoubles
 * @return {number}
 */
var minMoves = function(target, maxDoubles) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Moves to Reach Target Score — Problem & Solution

Minimum Moves to Reach Target Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Moves to Reach Target Score is a medium coding problem on math and greedy, asked in Amazon, Google and Walmart interviews.

  • Difficulty: Medium
  • Topics: Math, Greedy
  • Asked at: Amazon, Google, Walmart
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Minimum Moves to Reach Target Score

  1. Hint 1

    Work backwards from target down to 1 — then each step is forced rather than chosen.

  2. Hint 2

    An odd value can only have come from an increment, so subtract 1.

  3. Hint 3

    An even value should be halved while doublings remain; once they run out, everything left is increments.

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

Java

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

C++

int minMoves(int target, int maxDoubles) {
    int moves = 0;
    long long v = target;
    int doubles = maxDoubles;
    while (v > 1) {
        if (doubles == 0) return (int) (moves + v - 1);
        if (v % 2 == 1) v -= 1;
        else { v /= 2; doubles--; }
        moves++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Greedy Algorithms