Skip to main content
Talentd

Minimum Moves to Reach Target Score - Solution & Explanation

MediumMathGreedy18 min readAsked at: Amazon, Meta, Wayfair
Practice this problem

Problem Statement

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 <= 109
  • 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.

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

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.

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.

Code

PythonJava

Python

Java

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS SearchO(target)O(target)Conceptual approach for modeling operations as graph transitions or when exploring all reachable states
Greedy Backward StrategyO(log target)O(1)Optimal solution when minimizing operations with limited doubling; preferred in interviews

Video Solution

Minimum Moves to Reach Target Score | Leetcode 2139 | Leetcode Weekly Contest 276 Solution | Java • Pepcoding • 2,500 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Moves to Reach Target Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Steps to Reduce a Number in Binary Representation to One

Next

Number of Steps to Reduce a Number to Zero