Watch 10 video solutions for Minimum Moves to Reach Target Score, a medium level problem involving Math, Greedy. This walkthrough by Pepcoding has 2,481 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |