Minimum Moves to Reach Target Score
MedPrompt
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 = 19Example 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 <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach treats the problem as finding the shortest path in an implicit graph. The nodes of the graph are the integers we can reach, and the edges represent the allowed operations (increment and double). Since each operation has a uniform cost of 1, Breadth-First Search (BFS) is a natural fit for finding the minimum number of moves from the starting number 1 to the target.
Algorithm
- State Representation: Model the problem as a shortest path on a graph. Each state is defined by a pair
(current_value, doubles_used). - Initialization: Start a Breadth-First Search (BFS) from the initial state
(1, 0)withmoves = 0. - Data Structures: Use a queue to manage states to visit and a
Setto keep track of visited states to avoid redundant computations. - Traversal:
- Dequeue a state
(curr, doubles). - If
currequalstarget, return the current number of moves. - Generate next possible states:
- Increment: A new state
(curr + 1, doubles). - Double: A new state
(curr * 2, doubles + 1), only ifdoubles < maxDoubles.
- Increment: A new state
- For each new state, if it's within the
targetboundary and has not been visited, add it to the queue and the visited set.
- Dequeue a state
- Level-by-Level: Process the BFS level by level, incrementing the
movescount after each level is fully processed. This ensures finding the shortest path.
Walkthrough
We can solve this problem by exploring all possible sequences of operations in a breadth-first manner. This guarantees that we find the path with the minimum number of moves first. The state in our search needs to track not only the current number but also the number of double operations used, as this is a limited resource.
- We initialize a queue with the starting state
(value=1, doubles_used=0). - We also use a
visitedset to store states we have already processed to avoid getting into cycles or doing redundant work. A state is uniquely identified by both its value and the number of doubles used to reach it. - The BFS proceeds in levels. Each level corresponds to one additional move. In each step, we explore all possible next states from the states in the current level.
- From a state
(curr, doubles), we can transition to(curr + 1, doubles)(increment) and(curr * 2, doubles + 1)(double), provided the new value does not exceedtargetand we have not exhaustedmaxDoubles. - The first time we reach the
targetvalue, we are guaranteed to have done so in the minimum number of moves. However, due to the large constraints ontarget, this approach is not practical.
import java.util.Queue;import java.util.LinkedList;import java.util.Set;import java.util.HashSet;import java.util.Objects; class Solution { // This approach is illustrative but will time out for large inputs. class State { long value; int doubles; State(long value, int doubles) { this.value = value; this.doubles = doubles; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; State state = (State) o; return value == state.value && doubles == state.doubles; } @Override public int hashCode() { return Objects.hash(value, doubles); } } public int minMoves(int target, int maxDoubles) { if (target == 1) { return 0; } Queue<State> queue = new LinkedList<>(); Set<State> visited = new HashSet<>(); State startState = new State(1, 0); queue.add(startState); visited.add(startState); int moves = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); moves++; for (int i = 0; i < levelSize; i++) { State current = queue.poll(); // Try incrementing long nextValInc = current.value + 1; if (nextValInc == target) { return moves; } State nextStateInc = new State(nextValInc, current.doubles); if (nextValInc < target && !visited.contains(nextStateInc)) { visited.add(nextStateInc); queue.add(nextStateInc); } // Try doubling if (current.doubles < maxDoubles) { long nextValDouble = current.value * 2; if (nextValDouble == target) { return moves; } State nextStateDouble = new State(nextValDouble, current.doubles + 1); if (nextValDouble < target && !visited.contains(nextStateDouble)) { visited.add(nextStateDouble); queue.add(nextStateDouble); } } } } return -1; // Should not be reached }}Complexity
Time
O(target * maxDoubles). The number of states is `target * maxDoubles`. In the worst case, BFS would explore a significant fraction of these states. Given `target` can be up to 10^9, this approach is too slow.
Space
O(target * maxDoubles). The space is dominated by the `visited` set and the queue, which in the worst case could store a number of states proportional to the target value times the number of allowed doubles. This is infeasible for the given constraints.
Trade-offs
Pros
Conceptually straightforward for a shortest path problem.
Guaranteed to find the optimal solution if it could run to completion.
Cons
Extremely inefficient for large
targetvalues due to the massive state space.Will result in 'Time Limit Exceeded' or 'Memory Limit Exceeded' for the given constraints.
Requires a custom class or pair to represent the state, adding some implementation overhead.
Solutions
Solution
class Solution {public int minMoves(int target, int maxDoubles) { 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); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.