# Minimum Moves to Reach Target Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-moves-to-reach-target-score)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-reach-target-score
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Wayfair](https://scaleengineer.com/companies/wayfair)
---
## 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 <= 109`
* `0 <= maxDoubles <= 100`

# Approaches
## Brute-Force using Breadth-First Search (BFS)
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`.
**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.
**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 `target` values 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.
### Explanation
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 `visited` set 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 exceed `target` and we have not exhausted `maxDoubles`.
- The first time we reach the `target` value, we are guaranteed to have done so in the minimum number of moves. However, due to the large constraints on `target`, this approach is not practical.

```java
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
    }
}
```
### 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)` with `moves = 0`.
- **Data Structures**: Use a queue to manage states to visit and a `Set` to keep track of visited states to avoid redundant computations.
- **Traversal**: 
  1. Dequeue a state `(curr, doubles)`.
  2. If `curr` equals `target`, return the current number of moves.
  3. Generate next possible states:
     - **Increment**: A new state `(curr + 1, doubles)`.
     - **Double**: A new state `(curr * 2, doubles + 1)`, only if `doubles < maxDoubles`.
  4. For each new state, if it's within the `target` boundary and has not been visited, add it to the queue and the visited set.
- **Level-by-Level**: Process the BFS level by level, incrementing the `moves` count after each level is fully processed. This ensures finding the shortest path.

## Optimal Greedy Approach (Working Backwards)
A highly efficient and optimal solution can be found using a greedy approach by working backward from the `target` to `1`. Instead of building up from `1`, we deconstruct the `target` down to `1`. The inverse operations are subtracting 1 (the reverse of an increment) and halving (the reverse of a double). The key insight is that the `halve` operation is much more powerful. It's always better to use a `halve` operation on an even number if available, as it reduces the number much faster than a `decrement`.
**Time:** O(log(target)). The `target` value is halved in at most every two iterations of the loop. This logarithmic reduction leads to a very fast runtime, even for large `target` values. · **Space:** O(1). We only use a few variables to store the current target, moves, and remaining doubles, which requires a constant amount of space.
**Pros:** Extremely efficient with logarithmic time complexity.; Uses constant extra space.; Simple to implement once the greedy logic is understood.
**Cons:** The greedy logic of working backward might not be immediately intuitive.
### Explanation
The logic for this greedy strategy is based on the observation that to minimize moves, we should prioritize the `double` operation, which has a much larger effect than an `increment`. When working backward from `target`:

- If the current `target` is odd, it could not have been the result of a `double` operation. Therefore, the last move must have been an `increment`. So, we reverse this by decrementing `target` by 1, which costs one move.
- If the current `target` is even, it could have been reached from `target - 1` (by increment) or `target / 2` (by double). Reaching `target` from `target / 2` is always more efficient than reaching it from `target - 1`, as it gets us closer to our goal of `1` in a single step. Thus, if we have `maxDoubles` left, we should always choose to reverse the `double` operation by halving the `target`.

This process is repeated until `target` becomes `1` or we run out of `maxDoubles`. If we run out of `maxDoubles` before `target` reaches `1`, the remaining steps must all be increments, so we simply add `target - 1` to our move count.

```java
class Solution {
    public int minMoves(int target, int maxDoubles) {
        int moves = 0;
        
        // We can't use doubles once target is 1 or we run out of maxDoubles
        while (target > 1 && maxDoubles > 0) {
            if (target % 2 == 0) {
                // If target is even, it's optimal to divide by 2.
                // This corresponds to a "double" operation in the forward direction.
                target /= 2;
                maxDoubles--;
            } else {
                // If target is odd, we must have reached it by an increment.
                // So we reverse it by decrementing.
                target--;
            }
            moves++;
        }
        
        // If target is still greater than 1, it means we've used up all maxDoubles.
        // The rest of the moves must be increments from 1 to the current target.
        // The number of such moves is target - 1.
        if (target > 1) {
            moves += (target - 1);
        }
        
        return moves;
    }
}
```
### Algorithm
- **Strategy**: Work backward from `target` to `1`.
- **Inverse Operations**: The forward operations `increment` and `double` correspond to backward operations `decrement` and `halve`.
- **Initialization**: Start with `moves = 0` and `current_value = target`.
- **Greedy Loop**: While `target > 1` and `maxDoubles > 0`:
  - If `target` is even, it's always optimal to have reached it from `target / 2`. Perform the reverse operation: `target /= 2`, decrement `maxDoubles`, and increment `moves`.
  - If `target` is odd, the only possible previous step was an increment from `target - 1`. Perform the reverse: `target--`, and increment `moves`.
- **Final Steps**: After the loop, if `target > 1`, it means we have exhausted all `maxDoubles`. The remaining distance to `1` must be covered by increments. Add `target - 1` to the total `moves`.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
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);
  }
};

```

### Python

```python
class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int: if target == 1: return 0 if maxDoubles == 0: return target - 1 if target % 2 == 0 and maxDoubles: return 1 + self . minMoves(target >> 1, maxDoubles - 1) return 1 + self . minMoves(target - 1, maxDoubles)

```