# Find the Maximum Achievable Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-maximum-achievable-number)
Canonical: https://scaleengineer.com/dsa/problems/find-the-maximum-achievable-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
Given two integers, `num` and `t`. A **number** `x`is **achievable** if it can become equal to `num` after applying the following operation **at most** `t` times:

* Increase or decrease `x` by `1`, and _simultaneously_ increase or decrease `num` by `1`.

Return the **maximum** possible value of `x`.

**Example 1:**

**Input:** num = 4, t = 1

**Output:** 6

**Explanation:**

Apply the following operation once to make the maximum achievable number equal to `num`:

* Decrease the maximum achievable number by 1, and increase `num` by 1.

**Example 2:**

**Input:** num = 3, t = 2

**Output:** 7

**Explanation:**

Apply the following operation twice to make the maximum achievable number equal to `num`:

* Decrease the maximum achievable number by 1, and increase `num` by 1.

**Constraints:**

* `1 <= num, t <= 50`

# Approaches
## Brute Force with Recursive Simulation
This approach involves checking every possible number `x` starting from a high value and decreasing. For each `x`, we simulate the process to see if it can be made equal to `num` within `t` operations. The simulation is done using a recursive function that explores all possible outcomes.
**Time:** O(4^t)

The `isAchievable` function has a branching factor of 4 and a maximum depth of `t`. This leads to an exponential number of calls, making the complexity `O(4^t)`. The outer loop for `x` is negligible in comparison. · **Space:** O(t)

The space complexity is determined by the maximum depth of the recursion stack, which is `t`.
**Pros:** Simple to conceptualize as it directly models the problem statement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
We want to find the maximum achievable `x`. A simple strategy is to start checking from a large number and go downwards. The first number we find that is "achievable" will be our answer.

A safe upper bound to start from can be derived from the constraints. Since `num <= 50` and `t <= 50`, `num + 2*t` is at most `50 + 100 = 150`. We can start our search from a number like 200.

The core of this approach is the `isAchievable(current_x, current_num, steps_left)` function. This function checks if `current_x` and `current_num` can be made equal using `steps_left` operations.

```java
class Solution {
    public int theMaximumAchievableX(int num, int t) {
        // Start checking from a reasonably high number downwards.
        // num + 2*t is the actual answer, so starting there is efficient.
        // For a true brute-force, we might start from a hardcoded limit like 200.
        for (int x = num + 2 * t; x >= 1; x--) {
            if (isAchievable(x, num, t)) {
                return x;
            }
        }
        return -1; // Should not be reached
    }

    private boolean isAchievable(long currentX, long currentNum, int stepsLeft) {
        if (currentX == currentNum) {
            return true;
        }
        if (stepsLeft == 0) {
            return false;
        }

        // Explore all 4 possible operations
        if (isAchievable(currentX + 1, currentNum + 1, stepsLeft - 1)) return true;
        if (isAchievable(currentX + 1, currentNum - 1, stepsLeft - 1)) return true;
        if (isAchievable(currentX - 1, currentNum + 1, stepsLeft - 1)) return true;
        if (isAchievable(currentX - 1, currentNum - 1, stepsLeft - 1)) return true;

        return false;
    }
}
```
### Algorithm
- The main idea is to search for the maximum achievable number `x` by starting from a high value and iterating downwards.
- For each candidate `x`, we check if it's possible to make `x` and `num` equal in at most `t` steps.
- This check is performed by a recursive function, `isAchievable(currentX, currentNum, stepsLeft)`, which simulates the process.
- **`isAchievable` function logic:**
  - **Base Case 1:** If `currentX == currentNum`, they are equal, so we return `true`.
  - **Base Case 2:** If `stepsLeft == 0` and they are not equal, we've run out of operations, so we return `false`.
  - **Recursive Step:** The function explores all four possible operations by making a recursive call for each:
    1. `isAchievable(currentX + 1, currentNum + 1, stepsLeft - 1)`
    2. `isAchievable(currentX + 1, currentNum - 1, stepsLeft - 1)`
    3. `isAchievable(currentX - 1, currentNum + 1, stepsLeft - 1)`
    4. `isAchievable(currentX - 1, currentNum - 1, stepsLeft - 1)`
  - If any of these recursive calls return `true`, it means a path to equality exists, and the function returns `true`. Otherwise, it returns `false`.
- The first value of `x` (iterating downwards) for which `isAchievable` returns `true` is the maximum possible value.

## Brute Force with Memoized Simulation (DP)
This approach improves upon the brute-force simulation by using memoization (a form of dynamic programming) to avoid recomputing results for the same subproblems. The state of the recursion can be simplified by focusing on the difference between the two numbers, making memoization effective.
**Time:** O(t^2)

With memoization, each state `(diff, stepsLeft)` is computed only once. The number of states is `O(t^2)`, and each computation takes constant time. Thus, the check for a given `x` is `O(t^2)`. · **Space:** O(t^2)

The space is used for the memoization table. The number of `stepsLeft` is `t`. The range of `diff` values explored is also proportional to `t`, leading to `O(t^2)` states.
**Pros:** Significantly more efficient than the naive recursive approach.; Passes within the time limits for the given constraints.
**Cons:** More complex to implement than the direct mathematical formula.; Still performs more computation than necessary compared to the optimal O(1) solution.
### Explanation
The naive recursive simulation has many overlapping subproblems. For instance, the state `(x=10, num=8, steps=5)` might be reached through different sequences of operations. We can optimize this by caching the results.

The state of a subproblem is defined by `(currentX, currentNum, stepsLeft)`. However, the absolute values can grow large. A better state representation is `(diff, stepsLeft)`, where `diff = currentX - currentNum`. This significantly reduces the state space.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int theMaximumAchievableX(int num, int t) {
        // The outer loop is kept for the brute-force structure, but it will
        // find the answer on the first try if we start from num + 2*t.
        for (int x = num + 2 * t; x >= 1; x--) {
            Map<Long, Map<Integer, Boolean>> memo = new HashMap<>();
            if (isAchievable(x - (long)num, t, memo)) {
                return x;
            }
        }
        return -1;
    }

    private boolean isAchievable(long diff, int stepsLeft, Map<Long, Map<Integer, Boolean>> memo) {
        if (diff == 0) {
            return true;
        }
        if (stepsLeft == 0) {
            return false;
        }
        if (memo.containsKey(diff) && memo.get(diff).containsKey(stepsLeft)) {
            return memo.get(diff).get(stepsLeft);
        }

        // Explore possible changes to the difference
        boolean possible = isAchievable(diff, stepsLeft - 1, memo) ||
                         isAchievable(diff + 2, stepsLeft - 1, memo) ||
                         isAchievable(diff - 2, stepsLeft - 1, memo);
        
        memo.computeIfAbsent(diff, k -> new HashMap<>()).put(stepsLeft, possible);
        return possible;
    }
}
```
### Algorithm
- This approach builds upon the previous one by optimizing the recursive simulation with memoization to avoid redundant computations.
- The key observation is that the state of the simulation can be defined by the *difference* between `x` and `num`, rather than their absolute values.
- Let `diff = currentX - currentNum`. Each operation changes `diff` by `0`, `+2`, or `-2`.
- We use a memoization table (e.g., a HashMap or a 2D array) to store the results of `isAchievable(diff, stepsLeft)`.
- **`isAchievable` function with memoization:**
  - **Base Case 1:** If `diff == 0`, return `true`.
  - **Base Case 2:** If `stepsLeft == 0`, return `false`.
  - **Memoization Check:** Before computing, check if the result for the state `(diff, stepsLeft)` is already in the memo table. If so, return the stored value.
  - **Recursive Step:** Recursively call the function for the three possible outcomes of the difference:
    1. `isAchievable(diff, stepsLeft - 1)`
    2. `isAchievable(diff + 2, stepsLeft - 1)`
    3. `isAchievable(diff - 2, stepsLeft - 1)`
  - Store the result in the memo table before returning.

## Direct Mathematical Formula
The most efficient approach is to use a direct mathematical insight. By analyzing how the difference between `x` and `num` changes with each operation, we can derive a simple formula for the maximum achievable `x`.
**Time:** O(1)

The solution involves a single arithmetic calculation, which takes constant time. · **Space:** O(1)

No extra space is used that depends on the input size. The computation is done with a few variables.
**Pros:** Extremely efficient with constant time and space complexity.; Very simple and concise to implement.
**Cons:** Requires a mathematical insight that might not be immediately obvious.
### Explanation
Let's analyze the effect of a single operation on the difference `d = x - num`. An operation can change `d` by `0`, `+2`, or `-2`. This means that with each operation, we can change the difference by an even number.

For `x` to be achievable, it must be possible to make it equal to `num` after some number of operations, say `k` (where `k <= t`). This means their final difference must be zero. To bridge an initial difference of `x - num`, the total change must be `num - x`.

The most effective way to make `x` and `num` meet is to move them towards each other. If `x > num`, we use the operation `(x--, num++)`. This reduces their difference by 2. After `t` such operations, the total reduction in difference is `2 * t`.

This implies that the initial difference `|x - num|` can be at most `2 * t`. To find the maximum possible `x`, we assume `x` is larger than `num` and set their difference to the maximum possible value:

`x - num = 2 * t`

Solving for `x`, we get:

`x = num + 2 * t`

This gives us a direct formula to calculate the answer.

```java
class Solution {
    public int theMaximumAchievableX(int num, int t) {
        // Each operation can bring x and num closer by at most 2.
        // To cover the maximum initial distance in t steps, that distance is 2*t.
        // To maximize x, we assume x > num, so the initial difference is x - num.
        // Therefore, the maximum possible x is num + 2*t.
        return num + 2 * t;
    }
}
```
### Algorithm
- Analyze the effect of a single operation on the difference `d = x - num`.
  - `(x++, num++)` or `(x--, num--)`: `d` is unchanged.
  - `(x++, num--)`: `d` increases by 2.
  - `(x--, num++)`: `d` decreases by 2.
- In one operation, the distance `|x - num|` can be reduced by at most 2.
- To make `x` and `num` equal in `t` operations, the initial distance `|x - num|` must be coverable within `t` steps.
- The maximum distance that can be covered in `t` operations is `2 * t` (by reducing the distance by 2 in every step).
- Therefore, the initial distance must satisfy `|x - num| <= 2 * t`.
- We want to find the maximum possible `x`. This means we want to maximize `x` subject to the constraint `x - num <= 2 * t`.
- This gives the upper bound `x <= num + 2 * t`.
- The maximum value for `x` is thus `num + 2 * t`.
- This value is achievable: start with `x = num + 2t`. Apply the operation `(x--, num++)` for `t` times. `x` becomes `(num + 2t) - t = num + t`. `num` becomes `num + t`. They become equal.

# Solutions
### Java

```java
class Solution {
public
  int theMaximumAchievableX(int num, int t) { return num + t * 2; }
}

```

### CPP

```cpp
class Solution {
public:
  int theMaximumAchievableX(int num, int t) { return num + t * 2; }
};

```

### Python

```python
class Solution:
    def theMaximumAchievableX(
        self, num: int, t: int) -> int: return num + t * 2

```