2139. Minimum Moves to Reach Target Score Solution

The problem

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 = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.

Example 2:

Input: target = 19, maxDoubles = 2
Output: 7
Explanation: 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
Explanation: 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⁹
0 <= maxDoubles <= 100

Approach overview

Problem Overview: You start with a score of 1 and want to reach target. Two operations are allowed: increment the score by 1, or double the score. The doubling operation can only be used maxDoubles times. The goal is to reach exactly target using the minimum number of moves.

Approach 1: BFS Search (O(target) time, O(target) space)

This method models the problem as a shortest-path search. Treat every score as a node and each operation (+1 or *2) as an edge. Use Breadth-First Search (BFS) starting from score 1, pushing states into a queue along with the number of doubles used. For each state, generate the next scores by applying valid operations while keeping the score ≤ target. BFS guarantees the first time you reach target is with the minimum moves. This approach is easy to reason about but inefficient when target is large because the state space grows quickly.

Approach 2: Greedy Backward Strategy (O(log target) time, O(1) space)

The optimal strategy works backwards from target instead of building up from 1. If the current value is even and you still have remaining doubles, divide it by two. This simulates reversing a doubling operation. If the value is odd, subtract one to make it even, which reverses an increment operation. When you run out of doubling operations, the only option left is repeated decrements until the value reaches 1. Each step reduces the number quickly, giving a logarithmic number of operations.

This works because doubling is the most powerful operation available. By prioritizing division when reversing the process, you minimize the number of required steps. The logic fits well into greedy reasoning: always choose the move that reduces the target the fastest while respecting the remaining doubling limit. The arithmetic operations themselves rely on simple math observations about parity and powers of two.

Recommended for interviews: The greedy backward approach is what interviewers typically expect. It demonstrates that you can recognize when reversing the process simplifies the state space and leads to an O(log target) solution with constant memory. Mentioning the BFS formulation first can help show problem‑solving thinking, but implementing the greedy strategy proves strong algorithmic intuition.

Approach 1: Greedy Approach

In this approach, we work backward from the target to the initial value of 1. By starting from the target, we can better decide when to use the doubling operation. Our objective is to use the double operation effectively while minimizing increments.

The backward approach allows us to find a path with minimal moves by performing the inverse of the possible operations:

If the number is even and we have doubling opportunities left, we divide by 2.
If the number is odd, we subtract 1 to make it even and then consider doubling next time.

By applying these operations, we can ensure that we are reducing the number of moves strategically while managing the available double operations optimally.

Python

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

Java

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

C++

int minMoves(int target, int maxDoubles) {
    int moves = 0;
    while (target > 1) {
        if (maxDoubles > 0 && target % 2 == 0) {
            target /= 2;
            maxDoubles--;
        } else {
            if (maxDoubles == 0) {
                moves += (target - 1);
                break;
            }
            target--;
        }
        moves++;
    }
    return moves;
}

JavaScript

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

int minMoves(int target, int maxDoubles) {
    int moves = 0;
    while (target > 1) {
        if (maxDoubles > 0 && target % 2 == 0) {
            target /= 2;
            maxDoubles--;
        } else {
            if (maxDoubles == 0) {
                moves += (target - 1);
                break;
            }
            target--;
        }
        moves++;
    }
    return moves;
}

public int MinMoves(int target, int maxDoubles) {
    int moves = 0;
    while (target > 1) {
        if (maxDoubles > 0 && target % 2 == 0) {
            target /= 2;
            maxDoubles--;
        } else {
            if (maxDoubles == 0) {
                moves += (target - 1);
                break;
            }
            target--;
        }
        moves++;
    }
    return moves;
}

The function iteratively reduces the target towards 1. If the target is even and we have doubles remaining, we divide the target by two. If the target is odd, we decrement it by one to convert it to an even number for possible future halving. If no doubles are left, we simply subtract increments required to reach one.

Complexity

Time Complexity: O(log target), as we either divide the number or subtract from it, reducing the problem size quickly.

Space Complexity: O(1), as no extra space is used apart from a few variables.

Try this approach in the editor

Approach 2: BFS Approach

This approach leverages the Breadth-First Search (BFS) algorithm. We begin at position 1 and explore all possible next positions by either doubling or incrementing. The BFS ensures that we explore every state comprehensively layer by layer until we reach the target for the first time. We use a queue to keep track of the current state and the number of moves taken to reach that state.

The BFS approach naturally finds the shortest path in an unweighted graph, which aligns with finding the minimum number of moves in this problem.

Python

from collections import deque

def min_moves_bfs(target, maxDoubles):
    queue = deque([(1, 0, maxDoubles)])  # (current_value, moves, doubles_left)
    visited = set()
    while queue:
        current, moves, doubles_left = queue.popleft()
        if current == target:
            return moves
        if current in visited:
            continue
        visited.add(current)
        if current < target:
            queue.append((current + 1, moves + 1, doubles_left))
            if doubles_left > 0:
                queue.append((current * 2, moves + 1, doubles_left - 1))
    return -1

Java

import java.util.*;

public class Solution {
    public int minMovesBFS(int target, int maxDoubles) {
        Queue<int[]> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(new int[]{1, 0, maxDoubles});  // (current_value, moves, doubles_left)

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int value = current[0], moves = current[1], doubles_left = current[2];

            if (value == target) return moves;
            if (visited.contains(value)) continue;

            visited.add(value);

            if (value < target) {
                queue.offer(new int[]{value + 1, moves + 1, doubles_left});
                if (doubles_left > 0) {
                    queue.offer(new int[]{value * 2, moves + 1, doubles_left - 1});
                }
            }
        }
        return -1;
    }
}

The BFS solution uses a queue to perform level-order traversal through possible states. We enqueue each new state as a tuple consisting of its current value, the number of moves, and remaining double operations. BFS inherently explores states in ascending order of moves. It terminates as soon as a state matches the target, guaranteeing the solution uses the minimum moves.

Complexity

Time Complexity: O(target * maxDoubles), due to the potential exploration of all states within bound constraints.

Space Complexity: O(target * maxDoubles), as space could be occupied by each state derived.

Try this approach in the editor

Approach 3: 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.

If target=1, no operation is needed, and we can return 0 directly.

If maxDoubles=0, we can only use the increment operation, so we need target-1 operations.

If target is even and maxDoubles>0, we can use the doubling operation, so we need 1 operation, and then recursively solve target/2 and maxDoubles-1.

If target is odd, we can only use the increment operation, so we need 1 operation, and then recursively solve target-1 and maxDoubles.

The time complexity is O(min(log target, maxDoubles)), and the space complexity is O(min(log target, maxDoubles)).

We can also change the above process to an iterative way to avoid the space overhead of recursion.

TypeScript

function minMoves(target: number, maxDoubles: number): number {
    if (target === 1) {
        return 0;
    }
    if (maxDoubles === 0) {
        return target - 1;
    }
    if (target % 2 === 0 && maxDoubles) {
        return 1 + minMoves(target >> 1, maxDoubles - 1);
    }
    return 1 + minMoves(target - 1, maxDoubles);
}

func minMoves(target int, maxDoubles int) int {
	if target == 1 {
		return 0
	}
	if maxDoubles == 0 {
		return target - 1
	}
	if target%2 == 0 && maxDoubles > 0 {
		return 1 + minMoves(target>>1, maxDoubles-1)
	}
	return 1 + minMoves(target-1, maxDoubles)
}

Try this approach in the editor

Approach 4: Default Approach

TypeScript

function minMoves(target: number, maxDoubles: number): number {
    let ans = 0;
    while (maxDoubles && target > 1) {
        ++ans;
        if (target & 1) {
            --target;
        } else {
            --maxDoubles;
            target >>= 1;
        }
    }
    ans += target - 1;
    return ans;
}

func minMoves(target int, maxDoubles int) (ans int) {
	for maxDoubles > 0 && target > 1 {
		ans++
		if target&1 == 1 {
			target--
		} else {
			maxDoubles--
			target >>= 1
		}
	}
	ans += target - 1
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(log target), as we either divide the number or subtract from it, reducing the problem size quickly. Space Complexity: O(1), as no extra space is used apart from a few variables.
BFS Approach	Time Complexity: O(target * maxDoubles), due to the potential exploration of all states within bound constraints. Space Complexity: O(target * maxDoubles), as space could be occupied by each state derived.
Backtracking + Greedy	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
BFS Search	O(target)	O(target)	Conceptual approach for modeling operations as graph transitions or when exploring all reachable states
Greedy Backward Strategy	O(log target)	O(1)	Optimal solution when minimizing operations with limited doubling; preferred in interviews

Frequently asked questions

Is Minimum Moves to Reach Target Score easy or hard?

The problem is rated Medium on LeetCode. The operations themselves are simple, but the key insight is reversing the process and applying a greedy strategy. Recognizing this optimization is what elevates the difficulty.

Minimum Moves to Reach Target Score Python/Java solution

Most implementations follow the greedy backward logic. Track the number of remaining doubles and repeatedly reduce the target using division or subtraction. This implementation fits cleanly in Python, Java, C++, C#, or JavaScript with only a few lines of code.

How to solve Minimum Moves to Reach Target Score in O(log n)?

Start from the target and simulate reverse operations. If the target is even and you still have available doubles, divide it by two. If it is odd, subtract one to make it even. Once no doubles remain, simply subtract until the value becomes 1. Each step either halves the number or decreases it by one, leading to O(log n) time.

What is the best approach for Minimum Moves to Reach Target Score?

The greedy backward strategy is the optimal approach. Instead of building from 1 to the target, you work backward from the target value. If the number is even and doubles remain, divide by two; otherwise subtract one. This reduces the value quickly and runs in O(log target) time with O(1) space.

Is Minimum Moves to Reach Target Score asked at Google/Amazon/Meta?

Greedy math problems with reverse operations frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test whether candidates recognize that working backward simplifies the decision process and reduces complexity.

What data structure is used in Minimum Moves to Reach Target Score?

The optimal greedy solution does not require any complex data structure—only basic integer operations and counters. A BFS alternative uses a queue to explore reachable scores level by level, but this is less efficient for large targets.

What is the time complexity of Minimum Moves to Reach Target Score?

The optimal greedy solution runs in O(log target) time because the value is repeatedly halved whenever possible. Each halving drastically reduces the remaining work. The space complexity is O(1) since only a few variables are tracked.

Minimum Moves to Reach Target Score solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: BFS Approach

Approach 3: Backtracking + Greedy

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Moves to Reach Target Score solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: BFS Approach

Approach 3: Backtracking + Greedy

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems