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:
x = x + 1).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 <= 1090 <= maxDoubles <= 100Problem 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.
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:
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.
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
Minimum Moves to Reach Target Score | Leetcode 2139 | Leetcode Weekly Contest 276 Solution | Java • Pepcoding • 2,481 views views
Watch 9 more video solutions →Practice Minimum Moves to Reach Target Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor